[알고리즘] 2장. Divide and Conquer

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 2-1

* 분할정복(Divide-and-Conquer)식 설계 전략
- 분할(Divide) : 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.
- 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
- 통합(Combine) : (필요하다면) 해결된 해답을 모은다.
- 이러한 문제 해결 방법을 하향식(top-down) 접근방법이라고 한다.

 

* <A> 이분검색(binary search) : 재귀적방식

cpp

- 문제 : 크기가 n인 정렬된 배열 S에 x가 있는가?
- 입력 : 양수 n, 배열 S[1..n], 키 x
- 출력 : x가 S의 어디에 있는지의 위치. 만약 없으면, 0.

index location (index low, index high) {
‌index mid;
‌if (low > high)
‌‌return 0;
‌else {
‌‌mid = (low + high) / 2;
‌‌if (x == S[mid])
‌‌‌return mid;
‌‌else if (x < S[mid])
‌‌‌return location(low, mid - 1);
‌‌else
‌‌‌return location(mid + 1, high);
‌}
}
locationout = location(1, n);

* 꼬리 재귀호출(tail recursion)

- 재귀 알고리즘(recursive algorithm)에서 모든 재귀호출이 알고리즘의 마지막(꼬리)부분에서 이루어 지는 것이다. 이 알고리즘은 반복 알고리즘(iterative algorithm)으로 변환하기가 수월하다. 일반적으로 재귀 알고리즘은 재귀 호출할 때마다 그 당시의 상태를 활성 레코드(activation records) 스택에 저장해 놓아야 하는 반면, 반복 알고리즘은 그럴 필요가 없기 때문에 일반적으로 더 효율적이다(빠르다). 그렇다고 반복 알고리즘의 계산복잡도가 재귀 알고리즘보다 좋다는 의미는 아니다. 반복 알고리즘이 상수적(constant factor)으로만 좋다(빠르다)는 말이다.

* 반복대입법(iterative substitution or iteration)

* 추정 후 증명방법(substitution)

- 수학적귀납법을 사용.

---

📌 2-2

* <A> 합병정렬(mergesort)

cpp

- 문제 : n개의 정수를 비내림차순으로 정렬하시오.
- 입력 : 정수 n, 크기가 n인 배열 S[1..n]
- 출력 : 비내림차순으로 정렬된 배열 S[1..n]
- 보기 : 27, 10, 12, 20, 25, 13, 15, 22

void mergesort (int n, keytype S[]) {
‌const int h = n / 2, m = n - h;
‌keytype U[1..h], V[1..m];
‌if (n > 1) {
‌‌copy S[1] through S[h] to U[1] through U[h];
‌‌copy S[h+1] through S[n] to V[1] through V[m];
‌‌mergesort(h, U);
‌‌mergesort(m, V);
‌‌merge(h, m, U, V, S);
‌}
}

- 공간복잡도가 향상된 알고리즘
void mergesort2 (index low, index high) {
‌index mid;
‌if (low < high) {
‌‌mid = (low + high) / 2;
‌‌mergesort2(low, mid);
‌‌mergesort2(mid + 1, high);
‌‌merge2(low, mid, high);
‌}
}
mergesort2(1, n);

* <A> 합병(merge)

cpp

- 문제 : 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하시오.
- 입력 : (1) 양의 정수 h, m, (2) 정렬된 배열 U[1..h], V[1..m]
- 출력 : U와 V에 있는 키들을 하나의 배열에 정리한 S[1..h+m]

void merge(int h, int m, const keytype U[], const keytype V[], keytype S[]) {
‌index i, j, k;
‌i = 1; j = 1; k = 1;
‌while (i <= h && j <= m) {
‌‌if (U[i] < V[j]) {
‌‌‌S[k] = U[i];
‌‌‌i++;
‌‌}
‌‌else {
‌‌‌S[k] = V[j];
‌‌‌j++;
‌‌}
‌‌k++;
‌}
‌if (i > h)
‌‌copy V[j] through V[m] to S[k] through S[h+m];
‌else
‌‌copy U[i] through U[h] to S[k] through S[h+m];
}

- 공간복잡도가 향상된 알고리즘
void merge2(index low, index mid, index high) {
‌index i, j, k;
‌i = low; j = mid + 1; k = low;
‌while (i <= mid && j <= high) {
‌‌if (S[i] < S[j]) {
‌‌‌U[k] = S[i];
‌‌‌i++;
‌‌}
‌‌else	{
‌‌‌U[k] = S[j];
‌‌‌j++;
‌‌}
‌‌k++;
‌}
‌if (i > mid)
‌‌copy S[j] through S[high] to U[k] through U[high];
‌else
‌‌copy S[i] through S[mid] to U[k] through U[high];
‌copy U[low] through U[high] to S[low] through S[high];
}

* 제자리정렬(in-place sort) 알고리즘

- 추가적인 저장장소를 사용하지 않고 정렬하는 알고리즘

---

📌 2-3

* <A> 빠른정렬(Quicksort) : 분할 교환 정렬 (partition exchange sort)

cpp

- 문제 : n개의 정수를 비내림차순으로 정렬
- 입력 : 정수 n > 0, 크기가 n인 배열 S[1..n]
- 출력 : 비내림차순으로 정렬된 배열 S[1..n]

void quicksort (index low, index high) {
‌index pivotpoint;
‌if (high > low) {
‌‌partition(low, high, pivotpoint);
‌‌quicksort(low, pivotpoint - 1);
‌‌quicksort(pivotpoint + 1, high);
‌}
}

* <A> 분할(partition)

cpp

- 문제 : 빠른정렬을 하기 위해서 배열 S를 둘로 나눈다.
- 입력 : (1) 첨자 low, high (2) S의 부분배열 (첨자는 low에서 high)
- 출력 : 첨자 low에서 high까지의 S의 부분배열의 기준점(pivot point), pivotpoint

void partition (index low, index high, index& pivotpoint) {
‌index i, j;
‌keytype pivotitem;
‌pivotitem = S[low];
‌j = low;
‌for (i = low + 1; i <= high; i++) {
‌‌if (S[i] < pivotitem) {
‌‌‌j++;
‌‌‌exchange S[i] and S[j];
‌‌}
‌}
‌pivotpoint = j;
‌exchange S[low] and S[pivotpoint];
}

---

📌 2-4

* <A1.4> 행렬곱셈

cpp

- 문제 : 두 개의 n x n 행렬의 곱을 구하라.
- 입력 : 양의 정수 n, 수의 2차원 배열 A와 B. 여기서 이 행렬의 행과 열은 모두 1부터 n가지의 첨자를 갖는다.
- 출력 : A와 B의 곱이 되는 수의 2차원 배열 C. 이 행렬의 행과 열은 모두 1부터 n까지의 첨자를 갖는다.

for (i = 1; i < n; i++) {
‌for (j = 1; j < n; j++) {
‌‌C[i][j] = 0;
‌‌for (k = 1; k <= n; k++)
‌‌‌C[i][j] = C[i][k] + A[i][k] * B[k][j];
‌}
}

* <A> 쉬트라쎈(Strassen)의 방법
C = [M1 + M4 - M5 + M7, M3 + M5]
    [M2 + M4, M1 + M3 - M2 + M6]
M1 = (A11 + A22) X (B11 + B22)
M2 = (A21 + A22) X B11
M3 = A11 X (B12 - B22)
M4 = A22 X (B21 - B11)
M5 = (A11 + A12) X B22
M6 = (A21 - A11) X (B11 + B12)
M7 = (A12 - A22) X (B21 + B22)

cpp

- 문제 : n이 2의 거듭제곱일 때, n x n 크기의 두 행렬의 곱을 구하시오.
- 입력 : 정수 n, n x n 크기의 행렬 A와 B
- 출력 : 행렬 A 와 B의 곱인 C

void Strassen(int n, n*n_matrix A, n*n_matrix B, n*n_matrix& C) {
‌if (n <= 임계점)
‌‌단순한 알고리즘을 사용하여 C = A * B를 계산;
‌else {
‌‌A를 4개의 부분행렬 A11, A12, A21, A22로 분할;
‌‌B를 4개의 부분행렬 B11, B12, B21, B22로 분할;
‌‌쉬트라쎈의 방법을 사용하여 C = A * B를 계산;
‌‌// 되부르는 호출의 예 : Strassen(n/2, A11+A22, B11+B22, M1)
‌}
}

* 임계점

- 두 알고리즘의 효율성이 교차하는 문제의 크기

* n*n 행렬을 곱하는 두 알고리즘의 비교
- 곱셈 : 표준(n^3), 쉬트라센(n^2.81)
- 덧셈/뺄셈 : 표준(n^3-n^2), 쉬트라센(6n^2.81-6n^2)

* 두 개의 행렬을 곱하기 위한 문제에 대해서 시간복잡도가 Θ(n^2)이 되는 알고리즘을 만들어 낸 사람은 아무도 없다.
* +) 만들 수 없다고 증명한 사람도 없다.

---

📌 2-5

* 큰 정수 계산법

- 하드웨어의 용량을 초과하는 정수연산 - 천문학

* <A> 큰 정수 곱셈 (분할 정복법)

cpp

- 문제 : 2개의 큰 정수 u와 v를 곱하라
- 입력 : 큰 정수 u와 v, 크기 n
- 출력 : prod(u와 v의 곱)

large_integer prod(large_integer u, large_integer v) {
‌large_integer x, y, w, z;
‌int n, m;
‌n = maximum(u의 자리수, v의 자리수);
‌if (u == 0 || v == 0) return 0;
‌else if (n <= threshold)
‌‌return 일반적인 방법으로 구현 u x v;
‌else {
‌‌m = └n/2┘;
‌‌x = u divide 10^m; y = u mod 10^m;
‌‌w = v divide 10^m; z = v mod 10^m;
‌‌return prod(x, w) * 10^2m
‌‌‌+ (prod(x,z) + prod(w,y)) * 10^m + prod(y,z);
‌}
}

* <A> 큰 정수 곱셈 (분할 정복법) 2 - 개선된 방법

cpp

- 문제 : 2개의 큰 정수 u와 v를 곱하라
- 입력 : 큰 정수 u와 v, 크기 n
- 출력 : prod2(u와 v의 곱)

large_integer prod2(large_integer u, large_integer v) {
‌large_integer x, y, w, z, r, p, q;
‌int n, m;
‌n = maximum(u의 자리수, v의 자리수);
‌if (u == 0 || v == 0) return 0;
‌else if (n <= threshold)
‌‌return 일반적인 방법으로 구한 u * v;
‌else {
‌‌m = └n/2┘;
‌‌x = u divide 10^m; y = u mod 10^m;
‌‌w = v divide 10^m; z = v mod 10^m;
‌‌r = prod2(x+y, w+z);
‌‌p = prod2(x, w);
‌‌q = prod2(y, z);
‌‌return p*10^2m + (r-p-q)*10^m + q;
‌}
}

* 임계값 결정
- DivideAndConquer 방법에서 큰 문제를 어느 크기의 문제가 될 때까지 분할 할 것인가
- optimal threshold value를 결정하는 방법

* 분할정복을 사용하지 말아야 하는 경우
- 크기가 n인 입력이 2개 이상의 조각으로 분할되며, 분할된 부분들의 크기가 거의 n에 가깝게 되는 경우 => 시간복잡도 : 지수(exponential) 시간. ex) T(n) = 2T(n-1) + n
- 크기가 n인 입력이 거의 n개의 조각으로 분할되며, 분할된 부분의 크기가 n/c인 경우. 여기서 c는 상수다. => 시간복잡도 : n^lgn. ex) T(n) = nT(n/2) + n

* 도사 정리(The Master Theorem)
- T(n) = aT(n/b) + f(n)
- 위와 같은 형태를 가진 T(n)은 점근적인 한계점(asymptotic bound)을 가질 수 있다.

* 도사보조정리
- T(n) = aT(n/b) + cn^k
- T(1) = d
- T(n) => {Θ(n^k) (if a < b^k)
    {Θ(n^klgn) (if a = b^k)
    {Θ(n^logb(a)) (if a > b^k)
- T(n) <= aT(n/b) + cn^k
- T(n) => {O(n^k) (if a < b^k)
    {O(n^klgn) (if a = b^k)
    {O(n^logb(a)) (if a > b^k)
- T(n) >= aT(n/b) + cn^k
- T(n) => {Ω(n^k) (if a < b^k)
    {Ω(n^klgn) (if a = b^k)
    {Ω(n^logb(a)) (if a > b^k)

---