2장 Divide-and-Conquer

Divide & Conquer(분할정복식) 설계 전략

분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눔
정복(Conquer): 나눈 작은 문제를 각각 해결
통합(Combine): (필요하다면) 해결된 해답을 모음

재귀적(recursive) 방법으로 분할하고 정복하여 해결함

🤔 이러한 문제 해결 방법을 무엇이라고 할까요?

Top-Down(하향식) 접근 방식

구조 위주(모듈 단위)

⇒ 절차지향(구조적) 프로그래밍 (ex. C언어)

🤔 top-down 방식의 장점을 생각해봅시다.

Bottom-Up(상향식) 접근 방식

데이터 위주(객체 단위)

객체지향(데이터) 프로그래밍 (ex. C++, JAVA 언어)

🤔 bottom-up 방식의 장점을 생각해봅시다.

Divide & Conquer

Divide & Conquer을 사용한 알고리즘은 항상 재귀적인 알고리즘을 갖고 있습니다.

💡 Divide&Conquer 알고리즘을 의사 코드로 짜 봅시다.

procedure D&C(p, q)

int n, A(1:n);
int m, p, q;  /* 1≤p≤q≤n */
If SMALL(p, q) then return(G(q, p))
else 
{ m := DIVIDE(q, p)
  return COMBINE (D&C(p, m), D&C(m+1, p))
}

End if

Divide & Conquer 시간복잡도

T(n) = { g(n), if n is small enough

f(n) + 2T(n/2), otherwise

🤔 각각의 T(n), f(n), g(n)이 의미하는 바를 생각해봅시다.

Binary Search (이분검색)

Divide: breaking up three instances,
- I1= (S[1], S[2], …, S[k-1]), x), I2 = (S[k], x), I3 = (S[k+1], …, S[n], x)

Conquer:
- If x = S[k], then location = k
- If x < S[k], then only I1 remains to be solved (for I2 & I3, location = 0)
- If x > S[k], then only I3 remains to be solved (for I1 & I2, location = 0)
Merge: (필요 없음)

Recursive 알고리즘으로 나타낸 Binary Search

💡 Divide&Conquer 알고리즘을 의사 코드로 짜 봅시다.

index BYSRCH(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 BYSRCH(low, mid-1);  
		else
			return BYSRCH(mid+1, high);
    }
}

💡 배열 [ -30, -2, 0, 4, 7, 34, 64, 87, 99] 이고 X=64일 때 Binary Search로 풀어봅시다.

Analysis of Binary Search (recursive algorithm)

T(n) = { 1 if n=1

T(n/2)+1 if n>1

Let n = 2^k

T(n) = T(n/n) + k = 1 + k = 1 + logn ∈ O(logn) ➡ O(logn)

정렬 알고리즘

평균적으로 O(n^2) 시간이 소요되는 알고리즘
- 선택정렬
- 버블정렬
- 삽입정렬
평균적으로 O(n) 시간이 소요되는 알고리즘
- 합병정렬 (merge sort)
- 퀵정렬 (Quick sort)
- 힙정렬 (Heap sort)

합병정렬(Mergesort)

합병 정렬 (Merge Sort)은 입력이 2개의 부분 문제로 분할하며(divide), 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘
n개의 숫자들은 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분문제를 재귀적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병(merge)하여 정렬함
합병 과정이 문제를 정복(conquer)하는 것

void mergesort (in 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);
    }
}

🤔 입력 크기가 n = 8인 배열 A=[20, 90, 22, 12, 78, 33, 24, 19] 을 Mergesort로 정렬해봅시다.

Mergesort의 시간 복잡도 (최악의 경우)

T(n) = { c for n = 1 (c는 상수)

2T(n/2) + an for n > 1 (a는 상수)

Let n = 2^k

T(n) = nT(1) + ank = cn + ank = cn + anlogn ➡ O(nlogn)

Mergesort의 공간 복잡도 (최악의 경우)

제자리정렬(in-place sort) 알고리즘: 입력 저장 시 필요한만큼 저장소 사용, 추가로 더 사용하지 않음.

Mergesort 알고리즘은 입력인 배열 S이외 U와 V를 추가로 만들어 사용함.

Mergesort를 재귀호출할 때마다 크기가 S의 반이 되는 U와 V가 추가적으로 필요함.

추가적으로 필요한 저장소 크기: n + n/2 + n/4 + ... = 2n

➡ 2n ∈ O(n)

ITry