알고리즘 공부방

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