알고리즘 공부방

우선, $O(N^2)$ DP 풀이부터 살펴 보자. $dp[i]$ = $0$ ~ $i$ 구간에서 $i$를 끝으로 하는 lis의 최대 길이 $dp[i]$ = $0$ ~ $i-1$ 의 $j$ 에 대하여 $arr[i]>arr[j]$를 만족하고, $dp[j]+1$의 최대값을 만족한다. 여기서는 구현할 때 처음에 NEGINF, 끝에 INF 를 추가해서 구현하였고, 동시에 전 단계로의 선택 과정을 담아 복원까지 했다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int MAXN = 1000; const int INF = numeric_limits::max(); const int NEGINF = ..

문제 https://www.acmicpc.net/problem/8980 택배의 목록과 트럭의 용량이 정해져 있을 때 배달할 수 있는 택배의 최댓값을 구하는 문제이다. 풀이 회의실 문제와 비슷하다. 제일 일찍 도착하는 택배 부터 우선순위로 배정해야 한다. 문제를 살짝 변형시켜 s부터 e까지 가는 택배 n개가 있으면 s부터 e까지 가는 택배 1개의 선분이 n개 있는 것으로 생각하자. 이제 회의실에서 동시에 C개의 회의를 할 수 있는 회의실 문제로 바뀌었다. 마찬가지로 가장 먼저 끝나는 택배 S, 최적해 M1, M2, M3, ...가 있다고 하면 M1을 항상 S로 바꿔도 최적해 이므로 성립한다. 따라서 무조건 먼저 끝나는 택배를 우선순위로 선택해야 하며, 원래 문제와 똑같아 진다. 자명하다. *Tip : 내 ..

문제 https://www.acmicpc.net/problem/1449 이 문제 자체보다 다음의 변형된 문제에 주목하자. 회의실 배정 문제처럼 N개의 구간들이 주어질 때 이 구간들을 최소한으로 선택해 그 합집합이 전체 구간을 모두 덮을 수 있도록 해야 한다. 풀이 가장 왼쪽 점을 지나는 구간들 중 가장 오른쪽으로 멀리 뻗어 나가는 구간을 선택한다. 그리디 알고리즘이 아닌 다른 최적해의 구간 M1, M2, ... 이 있다고 가정하자. 이때 가장 왼쪽 점을 포함하는 구간들 중 제일 오른쪽으로 멀리 뻗어 나가는 구간은 S라 하자. M1과 S는 모두 제일 왼쪽 점을 포함하지만, S는 더 멀리 나가니, M1을 S로 바꿔도 최적해가 된다. 자명하다. 시간 복잡도 : $O(N)$ #include using names..

문제 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만 포함되어 있는 직사각형을 만들고, 좌우로 한칸씩 늘려가며 선택하며 답을 구한다. 답은 양 끝에서 더 큰 쪽으로 확장시켜 나가는 것이다. 물론 이 방법은 각 단계에서 최적의 선택을 해 나가는 그리디이다. 그리디 -> 증명 -> 귀류법 (!) 위 그림에서 그리디 알고리즘으로 선택한..

카라츠바 알고리즘의 간략한 설명이다. 원래 $a \times b$를 할 때 시간복잡도는 $O(N^2)$이다. (a, b의 길이는 모두 $N$) 이를 Divide & Conquer 로 줄일 수 있는데, 편의를 위하여 $N=20$이라 하자. 구현이 젤 중요하다. 1. LIM : 어느정도 이상은 카라츠바의 상수가 매우 크기 때문에 $O(N^2)$의 곱셈이 유리하다. 나는 이를 1000정도로 설정했다. 2. CUT : 이게 젤 중요하다. 그냥 각 자리 수를 벡터에 넣고 카라츠바를 돌리면 $O(N^{log3})$ 에 300,000을 넣은 값으로 10초 정도 걸려야 답이 나온다. 하지만 8자리씩 묶어서 넣으면 그만큼 N이 줄어듬으로 훨씬 낫다. 나는 이를 1e8정도로 설정해서 1억 진법을 따랐다. 3. 포인터 주고..

문제 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)$ #..