알고리즘/Algospot (14) 썸네일형 리스트형 [Queue] ITES [1. 문제설명] [2. 코드] [Stack] BRACKETS2 [1. 문제 설명] [2. 코드] [연결리스트] JOSEPHUS [1. 문제 설명]https://algospot.com/judge/problem/read/JOSEPHUS[2. 풀이 접근] [3. 코드] [부분 합] CHRISTMAS [1. 문제 설명]https://www.algospot.com/judge/problem/read/CHRISTMAS[2. 풀이 접근] [3. 코드] [동적 계획법] JLIS [1. 문제 재정의 및 추상화] [2. 해결 계획] 두 수열의 LIS 를 찾은 뒤 각각 합치면 해결 할 수 없다 LIS 를 구하는 재귀 함수의 입력을 두개로 늘려야 함 => 각 수열을 받기 위해 => A[indexA] 와 B[indexB] 에서 시작하는 합친 증가 부분 수열의 최대 길이를 구하는 함수 A[indexA] 와 B[indexB] 중 작은 쪽이 앞에 온다고 가정 이 증가 부분 수열의 다음 숫자는 두가지 경우가 존재 1. A[indexA +1] 이후 또는 2. B[indexA +1] 이후 수열 중 max(A[indexA], B[indexB]) 보다 큰 수 중 하나 => 증가 부분 수열이 되기 위해선 A[indexA], B[indexB] 보다 큰 값이 뒤에 와야 한다. [3. 계획 검증] [동적 계획법] WILDCARD [1. 문제 재정의 및 추상화] 와일드카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자 일치 시, 와일드카드 패턴이 파일명과 대응된다 말함 '?' 는 어떤 글자와도 대응된다 가정함 '*' 는 0글자 이상의 어떤 문자열에도 대응 됨. 주어진 와일드카드 패턴에 대응되는 문자열 출력 ex) 와일드카드 패턴 he?p 에 매치되는 문자열은 아래와 같다 heap, help helpp 는 ? 가 lp 에 대응 될 수 없기 때문이다 패턴이 아닌 문자열은 알파벳 대소문자와 숫자만으로 구성 됨. [2. 해결 계획] 완전 탐색 풀이 #include // w: 와일드카드 패턴 // s: 문자열 bool match(const std::string &w, const std::string &s) { int pos = 0;.. 동적 계획법 [1. 도입] 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다 다만, 어떤 부분 문제가 두 개 이상의 문제를 푸는데 사용 될 때 이 문제의 답을 한번만 계산 하고 향후 이 결과를 재활용하여 속도 향상을 노려볼 수 있다. 여기서 두 번 이상 계산 되는 부분 문제를 중복되는 부분 문제라 한다. [2. 메모이제이션] 한 번 계산한 값을 저장해두었다가 재활용하는 최적화 기법 참조적 투명 함수인 경우 적용 가능함 참조적 투명 함수란? => 입력이 고정되어 있을 때 그 결과가 항상 같은 함수 => 함수의 반환 값이 그 입력 값만으로 결정되는지의 여부를 참조적 투명성이라 함. [3. 메모이제이션 구현 패턴] 기저 사례를 먼저 처리 => 입력이 범위를 벗어난 경우, ... 가능한 경우 cache[] 를 모두 -1로.. [분할 정복] FENCE [1. 문제 재정의 및 추상화] 너비가 같은 N 개의 나무 판자에서 잘라낼 수 있는 많은 직사각형 중 가장 큰 직사각형의 넓이 단, 비스듬히 잘라 낼 수 없다. N 은 최대 20000 까지 주어짐 TestCase 는 최대 50 까지 주어짐 [2. 해결 계획] 완전 탐색에서 시작 left = 0 ~ right = N 까지 범위에서 최대 넓이를 찾고 left = 1 ~ right = N 까지 범위에서 최대 넓이를 찾고, ... 분할 정복으로 계산 한다면, A) 가장 넓은 직사각형이 중앙에서 왼쪽에 존재하는 경우 B) 가장 넓은 직사각형이 중앙에서 오른쪽에 존재하는 경우 C) 가장 넓은 직사각형이 왼쪽과 오른쪽에 걸쳐있는 경우 Case C 의 경우, 최초에는 중앙에 두개의 판자를 모두 덮을 수 있게 둘 중 최.. [분할 정복] QUADTREE [1. 문제 재정의 및 추상화] [2. 해결 계획] [3. 계획 검증] [4. 구현] #include #include #include // 좌상단으로 계속 재귀적으로 들어가다보면, // 언젠가 b, w 를 만나게 됨 // 그 다음 문자가 우상단에 위치하는 것 이므로 // 참조자 형태로 offset 을 받아서 업데이트 해야 함. std::string solve(const char quadtree[], int &offset) { assert(offset < strlen(quadtree)); const char head = quadtree[offset]; // 다음 구역을 확인하기 위해 // 먼저 offset 을 업데이트 함. offset++; if (head == 'b' || head == 'w') { co.. [완전 탐색] CLOCKSYNC [1. 문제 재정의 및 추상화] 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계가 연결되어 있다. 한 스위치를 누를때마다 연결된 시계는 3시간씩 앞으로 움직임 (3->6, 6->9, 9->12, 12->3) 모든 시계를 12시로 돌려놓기 위해 스위치를 눌러야 할 최소 횟수를 출력해야 함 불가능 할 경우 -1을 출력 [2. 해결 계획] 경우의 수가 아니라 최소 횟수를 계산해야 함 그러나 일단 시작은 완전 탐색에서 시작해보도록 스위치를 누르는 순서는 중요하지 않다? [3. 계획 검증] 동일한 스위치를 4번 누르면 결국 처음 상태와 같아짐. 따라서 완전탐색으로 진행 시 전체 경우의 수는 4^10=1,048,576 으로 완전 탐색으로도 충분해 보임 [4. 구현] #include #include #incl.. 이전 1 2 다음