알고리즘 - 분할정복법 (Divide and Conquer)

본 게시물은 경희대학교 한치근 교수님의 '알고리즘분석' 강의를 듣고 노트한 내용입니다.

---

분할정복식 설계 전략

분할(Divide)

문제를 여러개의 작은 부분으로 나눈다.

 

정복(Conquer)

나눈 문제를 해결한다.

 

통합(Combine)

해결된 해답을 모은다.

 

-> 하향식(Top-Down) 문제 해결 방법

 

이분 검색 (binary search)

크기가 n인 정렬된 배열 S에 x가 있는지 결정하는 문제

분할 - 배열을 반으로 나누어 중앙에 위치한 항목보다 크고 작음을 판단해 해당 배열 반쪽을 선택한다.

정복 - 선택된 반쪽 배열에서 x를 찾는다.

통합 - 필요없음

 

1. 입력파라미터인 n, S, x는 변하지 않는 값이므로 전역 변수 (global)로 선언해 메모리를 절약하라! 재귀호출에서는 인덱스만 넘겨준다!

 

2. 꼬리 재귀 알고리즘은 당시 상태를 스택에 저장해놓아야하지만, 반복 알고리즘으로 변환하면 그럴 필요가 없으므로 일반적으로 더 효율적이다. (상수적으로만 좋다라는 말)

 

최악의 경우 시간복잡도

 

경우1: 반쪽배열이 둘다 정확히 n/2개일때

W(n) = log n + 1

(추정후 증명방법, 반복대입법 등으로 증명가능)

 

경우2: 일반적인 경우

n이 짝수일 때

n이 홀수일 때

따라서

 

저 꺽쇠는 뭔가?

마루함수 (floor function)

 

마루함수 3.1 = 3, 마루함수 -3.1 = -4

 

천장함수 (ceiling function)

 

천장함수 2.5 = 3, 천장함수 -4.7 = -4

 

합병정렬(merge sort)

문제: n개의 정수를 비내림차순으로 정렬

입력: 정수 n, 크기 n인 배열 S[1,,,n]

출력: 비내림차순으로 정렬된 배열 S

 

각각 정렬된 배열 뭉치를 합치는 알고리즘

 

합병(merge)

최악의 경우 시간복잡도

공간복잡도

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

n+n/2+n/4 ... = 2n

 

배열 S에서 인덱스를 움직여 U에 입력한 뒤, 이를 다시 S에 복사한다.

합병 알고리즘에서는 분할 과정에서 생긴 공간을 재활용한다.