알고리즘 공부방

카라츠바 알고리즘의 간략한 설명이다. 원래 $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], ..