알고리즘 공부방

문제 https://www.acmicpc.net/problem/2437 주어진 무게의 추들 중에 몇개를 골라 만들 수 없는 최소의 무게를 구하는 문제이다. 풀이 언뜻 봐서는 dp 문제인듯 하지만, 실제로는 그리디 문제이다. 주어진 추들로 측정할 수 없는 최소 무게를 구하는 것이기 때문에 parametric search 로는 안된다. 핵심은 이를 파악하는 것이다. 정렬된 추의 무게 a1, a2, a3, ... 이 있을 때 S = a1+a2+...+ai-1 까지의 무게는 모두 만들 수 있다고 가정하자. 만약 S+1 보다 ai이 더 크다면 S+1은 어떤 방법으로도 만들 수 없다. 크지 않다면 S+ai까지 모든 무게를 만들 수 있다. 이를 귀납적으로 풀면 된다. 시간 복잡도 : $O(NlogN)$ #includ..

문제 https://www.acmicpc.net/problem/1931 주어진 구간들 중 겹치지 않도록 최대한 많이 고르는 문제이다. 풀이 그리디 알고리즘은 3개의 단계만 뚫으면 풀린다. 1. 어떻게 해서든지 직관적으로 그리디 알고리즘 세우기 2. 탐욕적 선택 속성 증명 ( Greedy Choice Property) 3. 최적 부분 구조 증명 (Optimal Substructure) 일단 이 문제는 끝나는 시간이 빠른 순으로 회의를 선택해 나가야 한다. (귀류법) 끝나는 시간이 젤 빠른 S를 선택하지 않은 최적해가 존재한다 가정하자. 이 최적해의 회의는 M1, M2, ... 으로 구성될 것이다. 이때 당연히 M1은 S보다 끝나는 시간이 느리고, M2는 M1다음에 위치하니, S의 끝나는 시간보다 늦게 시작..

문제 https://www.acmicpc.net/problem/1725 히스토그램에서 최대 넓이의 직사각형을 찾는 문제이다. 풀이 i부터 j까지 선택을 하면 \( (j-i+1)\times min({A[i], …, A[j]}) \) 가 넓이가 된다. (s, e)의 답을 구하기 위해서 (s, mid), (mid+1, e) 의 답은 재귀로 구하고, 왼쪽 부분문제와 오른쪽 부분문제에 걸쳐 있는 답만 구하자. 처음에는 mid, mid+1만 포함되어 있는 직사각형을 만들고, 좌우로 한칸씩 늘려가며 선택하며 답을 구한다. 답은 양 끝에서 더 큰 쪽으로 확장시켜 나가는 것이다. 물론 이 방법은 각 단계에서 최적의 선택을 해 나가는 그리디이다. 그리디 -> 증명 -> 귀류법 (!) 위 그림에서 그리디 알고리즘으로 선택한..

문제 https://www.acmicpc.net/problem/2104 https://www.acmicpc.net/problem/1989 주어진 배열에서 \( (A[i]+…+A[j])\times min({A[i], …, A[j]}) \) 가 최대가 되도록 고르는 문제이다. 풀이 이 문제는 \( min({A[i], …, A[j]}) \) 를 곱한다는 면에서 히스토그램 문제와 매우 유사하다. (!!!) 따라서 이문제는 그냥 히스토그램 변형 문제이다. 이와 같이 히스토그램을 설정하되, 모든 그래프는 정사각형이라 하면 문제의 조건을 만족한다. 또한, 증명도 각 정사각형을 가로 길이 1의 도막으로 쪼개 적용하면 똑같이 성립함을 알 수 있다. 구현은 히스토그램과 거의 똑같다. 시간 복잡도 : $O(NlogN)$ #..