[Algorithm] 4. Divide and Conquer

✔️ Divide and Conquer?

1) 전략

- 주어진 문제의 입력을 분할하여 문제를 해결하는 방식

- 분할한 입력에 대해 동일 알고리즘을 적용하여 해 계산, 이들의 해를 취합하여 원래 문제의 해 얻음

- 부분문제(subproblem): 분할된 입력에 대한 문제, 부분해: 부분문제의 해

- 부분문제는 더이상 분할할 수 없을 때까지 계속 분할

 

2) 과정

- 분할(divide): 해결되기 쉽도록 문제를 여러 개의 작은 부분으로 나눔

- 정복(conquer): 나눈 작은 문제를 반복하여 각각 해결 (Top-Down)

- 통합(combine): 해결된 작은 답들을 모아 원래 문제의 해답 구함 (Bottom-Up)

 

3) 종류

- Sorting: merge sort, quick sort

- Binary tree traversal

- Multiplication of larget integers (카라추바 알고리즘)

- Matrix multiplication (Strassen 알고리즘)

- Closest-pair algorithm

- Convex-hull algorithm

---

✔️ Sorting (Merge Sort & Quick Sort)

1) Merge Sort (합병 정렬)

1. 분할: n개의 숫자들을 n/2개씩 2개의 부분문제로 분할

2. 정복: 부분문제 해결 (sub-problem 정렬)

3. 통합: 정렬된 각 부분배열을 하나의 정렬된 배열로 재귀적으로 합병

2) Quick Sort (빠른 정렬)

- [Pivot보다 작은 수들] [Pivot] [Pivot보다 큰 수들]

- 분할된 부분문제들에 동일 과정 재귀적으로 수행하여 정렬

---

✔️ Binary Tree Traversal

1) Pre-order (Root, Left, Right)

F - B - A - D - C - E - G - I - H

 

2) In-order (Left, Root, Right)

A - B - C - D - E - F - G - H - I

 

3) Post-order (Left, Right, Root)

A - C - E - D - B - H - I - G - F

 

1. 분할: 왼쪽 subtree, 오른쪽 subtree

2. 정복: traversal (in-order traversal)

- 왼쪽 subtree traverse

- root 방문

- 오른쪽 subtree traverse

3. 통합: X

---

✔️ Karatsuba Algorithm

1) Multiplication of larget integers

- 큰 수에 대한 효과적인 곱셈 알고리즘 (일반적으로 수가 2^320 이상일 때 효과적임)

- 자릿수가 같은 두 수에 대한 알고리즘 (다르면 적용 불가)

- x, y: B진법의 n자리수 어떤 값

- 기본적으로 x * y 곱셈연산은 O(n^2) 연산 횟수 필요

- x, y의 곱을 자릿수가 x, y의 절반인 수들의 곱 3번과 덧셈, 시프트 연산 이용해 연산 횟수 줄임

 

2) Algorithm

- 일반적으로 x, y가 n자리수인 경우 m = n/2

- ex)

        48 * 53

        L = 20 / N = 24 / M = 20 + 24 - (4 - 8)(5 - 3) = 52

        xy = 20 * 10^2 + 52 * 10^1 + 24 = 2544

        → 3번의 곱셈

---

✔️ Strassen's Matrix Multiplication

1) Strassen's Matrix Multiplication

- 조건: 행렬 nxn이며 n은 2의 거듭제곱임

1. 분할: A, B 행렬 분할

2. 정복: M1 ~ M7 구하기 위해 재귀 호출

3. 통합: 최종값 C 구함

 

2) Formula

- A 행렬 가로 성분 불러오는 데 for문 1번, B 행렬 세로 성분 불러오는 데 for문 1번, 각 성분 불러오면서 for문 1번 (n^3)

- n 값이 조금만 늘어나더라도 계산량이 기하급수적으로 증가

---

✔️ Closest-Pair Algorithm

1) Closest-Pair Algorithm

- 2차원 평면상 n개의 점 주어질 때, 거리가 가장 가까운 한 쌍의 점 찾는 문제

- 점이 아주 많을 때 효과적임

1. 점들을 하나의 차원을 기준으로 정렬 (ex. x-axis 기준)

2. 점들을 분할

3. 분할한 곳 각각에서 가까운 한 쌍의 점 찾음

4. 그 중 최소값 찾음

 

- 가장 가까운 두 점이 서로 다른 영역에 있다면?

→ 우선 최소값을 찾고, 각 영역에서 최소값 이내에 근접 점이 있는지 확인

- 더 좋은 방법은 최소 단위로 쪼개 최소값이 trivial 하도록 하는 것!

 

2) Closest Pair by Divide & Conquer

1. 분할: x-coordinate 기준으로 반으로 나눔 (점들을 반으로 나누는 vertical line 찾기)

2. 정복: 재귀적으로 반으로 쪼개진 영역에서 closest pair을 찾음

3. 통합: 구한 최소값보다 더 가까이에 점이 위치해 있는지 확인

- 활용 분야: 컴퓨터 그래픽스, 컴퓨터 비전, 지리 정보 시스템, 분자 모델링, ...

 

---

✔️ Convex Hull

1) Convex Hull

- 최소 개수의 꼭짓점으로 이루어진 볼록 다각형을 만들어, 볼록 다각형 내부에 모든 점을 포함

- H is the smallest convex polygon that contains all the points of Q

1. y 좌표가 가장 작은 것을 기준점으로 선정

2. 이 기준점으로 하여 다른 점들을 반시계 방향으로 정렬

3. 조건을 만족하지 않는 경우 pop

 

2) Convex Hull with Divide & Conquer

1. 분할: 점들을 둘로 분할 (Qleft, Qright)

2. 정복: Qleft, Qright에 대해 문제 해결

3. 통합: Qleft, Qright의 convex hull들을 병합

 

3) Algorithm

1. 점들을 두 영역으로 나눔

2. 각 영역에서 convex hull 구함

3. 왼쪽에서는 가장 오른쪽에 있는 점, 오른쪽에서는 가장 왼쪽에 있는 점을 연결

4. 오목인지 볼록인지 따지고, 조건 만족하지 않으면 점을 버리고 다음 점 선택해 연결