알고리즘 공부방

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

문제 https://www.acmicpc.net/problem/1517 버블 소트에서 발생하는 swap 의 수를 세는 문제이다. 풀이 결론부터 말하자면 inversion 들의 수를 세는 문제라고 할 수 있다. 버블 소트의 특징 중에는 한번 포문을 돌 때마다 젤 큰 수가 마지막으로 옮겨 간다는 성질이 있다. 이를 이용해, 잘 생각해 보면 swap 의 수는 배열 안의 각 수에 대하여 그 수보다 오른쪽에 있는 수들 중 그 수보다 작은 수들의 개수라 할 수 있다. 아직 $O(N^2)$ 이니, 조금 더 개선 해 보자. 일단 히스토그램 문제처럼, $(s, e)$ 구간을 $(s, mid)$, $(mid+1, e)$ 구간으로 나눌 수 있다. 그럼 재귀적으로 다 해결되고, $(s, mid)$ 의 구간의 각 수에 대하여 ..

문제 https://www.acmicpc.net/problem/2263 이진트리에서 중위순회 + 전위순회 or 후위순회 의 결과가 주어졌을 때 나머지 하나를 출력하는 문제이다. 풀이 분할정복 분야에서 꽤 유명한 문제이다. 전위순회 or 후위순회로는 해당하는 트리에서의 루트를 구할 수 있고, 중위순회로는 구한 루트를 기준으로 왼쪽, 오른쪽 서브트리를 구할 수 있다. 이때 전위순회 or 후위순회 에서는 i번째 노드가 순회된 순서를 저장해놔야 루트를 O(1) 만에 구할 수 있다. 시간 복잡도 : $O(N)$ #include using namespace std; typedef long long ll; typedef pair pii; #define MAXN 100000 int n; int in[MAXN+10], ..

문제 https://www.acmicpc.net/problem/11728 정렬된 두 배열이 주어지면, 그 두 배열을 병합한 결과를 출력하는 문제이다. 풀이 기본적인 머지소트에 필요한 병합 과정이다. 두 배열에서 더 작은 것을 골라 출력하면, 결과적으로 정렬된 배열이 완성된다. 풀이보다는 구현 자체를 익숙해지도록 하자. 시간 복잡도 : $O(N+M)$ #include using namespace std; typedef long long ll; typedef pair pii; #define MAXN 1000000 int n, m, a[MAXN+10], b[MAXN+10]; int main() { ios_base::sync_with_stdio(false); int i; scanf("%d%d", &n, &m);..