Ch.02 Divide and Conquer (분할정복)

Presentation on theme: "Ch.02 Divide and Conquer (분할정복)"— Presentation transcript:

1 Ch.02 Divide and Conquer (분할정복)
[CPA340] Algorithms and Practice Youn-Hee Han

2 Divide-and-Conquer - 유래
유래: 1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략 오스트리아-러시아 연합군 > 프랑스군 (15,000명 이상 많음)  전체적인 전력은 연합군이 프랑스군에 비해 우수함 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나눔  Divide 둘로 나뉜 연합군을 한 부분씩 정복(격파)함  Conquer

3 Divide-and-Conquer 설계 전략
각 작은 부분의 문제는 원래의 문제와 같은 속성을 지님 정복(Conquer): 나눈 작은 문제를 각각 해결한다. 작은 부분에서 정복이 어렵거나 불가능하면 더 작은 부분으로 나눈다. 즉, 분할 단계로 다시 이동한다 (재귀호출 사용 가능) 통합(Combine): (필요하다면) 해결된 해답을 모은다.  이러한 문제 해결 방법을 하향식(top-down) 접근방법이라고 한다.

4 이진(이분) 검색: 재귀 알고리즘 (1/3) 문제: 크기가 n인 정렬된 배열 S에 x가 있는지를 결정하라.
입력: 자연수 n, 정렬된 배열 S[1..n], 찾고자 하는 항목 x 출력: locationout – 배열 S에서의 x의 위치, 만약 x가 S에 없다면 0 설계전략: x가 배열의 중간에 위치한 항목과 같으면, “빙고, 찾았다!” 그렇지 않으면: [분할] 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택하고, 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택한다. [정복] 선택된 반쪽 배열에서 x를 찾는다. [통합] (필요 없음)

5 이진(이분) 검색: 재귀 알고리즘 (2/3) [알고리즘 2.1] (P.49) // S와 x를 전역적으로 선언...
locationout = location(1, n); ... 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); // 오른쪽 반 선택 }

6 이진(이분) 검색: 재귀 알고리즘 (3/3) 찾고자 하는 x 값이 18일 때...

7 이진 검색: 알고리즘 고찰 (1/2) 재귀함수의 파라미터와 지역변수는 어떻게 정하나?
입력 파라미터 n, S, x를 전역변수로 정할까 지역변수로 정할까? 입력 파라미터 n, S, x는 알고리즘 수행 중 변하지 않는 값 함수를 재귀호출(recursive call)할 때 마다 이렇게 변하지않는 파라미터를 가지고 다니는 것은 낭비이다. 그러므로, 전역변수로 정한다. low와 high 는? 함수 재귀호출시마다 변하는 값 함수 파라미터  일종의 지역변수

8 이진 검색: 알고리즘 고찰 (2/2) 꼬리 재귀호출(tail recursion) 재귀 알고리즘 vs. 반복 알고리즘
재귀 알고리즘에서 모든 재귀호출이 알고리즘의 마지막(꼬리) 부분에서 이루어지는 경우 꼬리 재귀호출 알고리즘은 반복 알고리즘(iterative algorithm)으로 변환하기가 수월하다. 재귀 알고리즘 vs. 반복 알고리즘 재귀 알고리즘은 재귀 호출할 때마다 그 당시의 상태를 활성화 레코드(activation records) 스택에 저장해 놓아야 한다. 반면에, 반복 알고리즘은 그럴 필요가 없기 때문에 일반적으로 더 효율적이다(빠르다). 일부 언어(LISP)는 컴파일러가 자동으로 재귀 프로그램을 반복 프로그램으로 바꾸어 준다.

9 이진 검색: 최악의 경우 시간 복잡도 (1/4) 단위연산: x와 S[mid]의 비교
입력 크기: 배열의 크기 n (= high - low + 1) 단위 연산으로 설정한 조건문을 함수 호출마다 각각 두 번(==, <) 수행하나, 사실상 비교는 한번 이루어진다고 봐도 된다. 그 이유는: (1) 어셈블리어(또는 기계어)로는 하나의 조건 명령으로 구현될 수 있기 때문; (2) x를 찾기 전까지는 항상 두 개의 조건 문을 수행하므로 하나로 묶어서 한 단위로 취급을 해도 되기 때문 분석 방법 모든 경우 분석이 가능한가? 아니면 최악 분석 사용  이와 같이 단위연산은 최대한 효율적으로(빠르게) 컴파일 및 실행된다고 일반적으로 가정하여 같은 류의 단위연산들은 하나의 단위로 취급해도 된다.

10 이진 검색: 최악의 경우 시간 복잡도 (2/4) [개략적 분석] 즉, n > 1 이고, n = 2k(k  1) 일 때…
한번 재귀호출할 때 마다 문제의 크기가 (대략) 절반으로 줄어든다. 예를 들어, n=32이면, mid=(1+32)/2 =16 이 되어 다음에 검색할 배열의 크기는 대략 처음의 절반이 된다. 또한, 예를 들어… 만약 찾고자 하는 키값이 배열의 첫번째에 있다면… mid=(1+32)/2 =16 mid=(1+15)/2 =8 mid=(1+7)/2 =4 mid=(1+3)/2 =2 …

11 이진 검색: 최악의 경우 시간 복잡도 (3/4) 그러므로, 시간 복잡도를 나타내 주는 점화식(recurrence)은 다음과 같다고 볼 수 있다. 위와 같은 W(n)의 점화식은 왼편의 과정을 거쳐서 W(n)의 닫힌 형태(Closed Form)식을 구할 수 있다. 재귀 호출 전의 단위연산 호출 횟수 재귀 호출 내에서의 단위연산 호출 횟수

12 이진 검색: 최악의 경우 시간 복잡도 (4/4) n = 2k(k  1) 라는 제한 조건이 없다면?
why? (p.83. 연습문제 4) 한편, 즉, 재귀적 이진 검색의 점근적 복잡도는 O(lg n) 이다.

13 더욱 정확한 분석 (1/4) [정확한 분석 (p.83. 연습문제 4)] 일반적인 경우
n에 대해서 중간 인덱스는 이 되며, 이 때 각 부분배열의 크기는 다음과 같다. 위의 표에 의하면 알고리즘이 다음 단계에 찾아야 할 항목의 개수는 많아야 개가 된다. 따라서 다음과 같은 점화식으로 표현할 수 있다. N 왼쪽 부분배열의 크기 mid 오른쪽 부분배열의 크기 짝수 n/2 - 1 1 n/2 홀수 (n-1)/2

14 더욱 정확한 분석 (2/4) 앞서 제시된 점화식의 해가 이 됨을 증명한다. 증명 방법: 수학적 귀납법
앞서 제시된 점화식의 해가 이 됨을 증명한다. 증명 방법: 수학적 귀납법 Induction basis: n = 1이면, 다음이 성립한다. Induction hypothesis: n > 1이고, 1 < k < n인 모든 k에 대해서, 가 성립한다고 가정한다.

15 더욱 정확한 분석 (3/4) Induction step: 1) n이 짝수이면 (즉, ), 다음이 성립한다.

16 더욱 정확한 분석 (4/4) 따라서, 모든 n에 대해서 이 성립한다.
Induction step: 2) n이 홀수이면 (즉, ), 다음이 성립한다. 따라서, 모든 n에 대해서 이 성립한다.

17 합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오.
입력: 정수 n, 크기가 n인 배열 S[1..n] 출력: (비내림차순으로) 정렬된 배열 S[1..n] 사용 알고리즘: 합병 정렬 (Merge Sorting) 각 단계별로 두 그룹의 정렬된 데이터를 서로 합쳐서 정렬된 더 큰 그룹으로 만들어 나아가는 정렬

18 합병정렬(Merge Sort) (2/2) 설계 전략
[분할] 배열을 반으로 나누어서 2 개의 부분배열로 분할한다. 각 부분 배열의 크기가 1일 될때까지 계속하여 분할한다. [정복] 가장 작은 수의 인접한 부분 배열 2개로 부터 정렬된 1개의 배열을 얻어낸다. [통합] 정렬된 부분 배열들을 합병하여 하나의 정렬된 배열로 만든다.

19 합병정렬: 알고리즘 void mergesort (int n, keytype[] S){ if (n > 1) {
final int h =  n/2 , m = n - h; keytype[] U = new keytype[1..h]; keytype[] V = new keytype[1..m]; 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); }

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

21 합병정렬: 합병 알고리즘 (1/2) [알고리즘 2.3] (P.55)
void merge(int h, int m, keytype[] U, 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]; i=1 j=1 j=2 i=3 j=3 i=5

22 합병정렬: 합병 알고리즘 (2/2) 알고리즘 2.3 설명 각 서브 그룹당 포인터 한 개씩 필요 (i 와 j)
각 포인터가 가리키는 데이터 두 개를 비교하여 더 작은 것을 S 배열에 복사 복사한 것에 대해서는 포인터를 다음으로 움직임 (i++ or j++) 두 그룹 중 하나는 먼저 처리가 완료되어 포인터가 밖으로 나감 (while (i <= h && j <= m) {…}) 남은 그룹의 데이터를 순서대로 S 배열의 남은 저장공간으로 그대로 복사 (while 절 이후…)

23 합병정렬: 최악의 경우 시간 복잡도 (1/3) 최악의 경우 [알고리즘 2.3]의 시간 복잡도 분석
단위연산: U[i]와 V[j]의 비교 입력크기: 2개의 입력 배열에 각각 들어 있는 항목의 개수: h, m 분석: i = h이고, j = m인 상태로 루프(loop)에서 빠져 나가는 것이 최악의 경우임 이때, 단위연산 의 실행 횟수는 h + m – 1 이다. 따라서, 최악의 경우 합병하는 시간복잡도는 W(h,m) = h + m – 1

24 합병정렬: 최악의 경우 시간 복잡도 (2/3) 최악의 경우 [알고리즘 2.2]의 시간 복잡도 분석
단위연산: merge() 함수 입력크기: 배열 S에 들어 있는 항목의 개수 n(=h+m) 분석 1): 최악의 경우 수행시간은 W(n) = W(h) + W(m) + h + m – 1 이 된다. W(h)는 U를 정렬하는데 걸리는 시간 W(m)은 V를 정렬하는데 걸리는 시간, h + m – 1 은 합병하는데 걸리는 시간 정수 n을 2k(k  1)이라고 가정하면, h = m = n/2 이 된다.

25 합병정렬: 최악의 경우 시간 복잡도 (2/3) (p.556)

26 합병정렬: 최악의 경우 시간 복잡도 (3/3) 분석 2):
n이 2의 거듭제곱(power)의 형태가 아닌 경우의 점화식은 다음과 같다. 그러나, 이 점화식의 정확한 해를 구하기는 복잡하다. [부록 B]의 p.562에 있는 eventually nondecreasing 및 smooth 정의에 의해 W(n)이 n에 대해 (궁극적으로, eventually) 감소하지 않는다. f(n)=nlgn은 유연하다 (smooth) 또한, [부록 B]의 p.562에 있는 정리 B.4 에 의해, 앞서 n = 2k라고 가정해서 얻었던 이 식을 임의의 양의 정수 n에 대해서도 그대로 활용할 수 있다. 즉, 임의의 n에 대하여 다음을 만족한다.

27 합병정렬: 공간 복잡도 (1/3) 그러면 합병정렬 알고리즘은 얼마만큼의 추가적인 저장장소가 필요할까?
함수 mergesort를 호출할 때마다 크기가 S의 절반이 되는 U, V가 추가로 필요. 함수 merge에서는 U와 V가 주소로 전달이 되어 그냥 사용되므로 추가적인 저장장소를 만들지 않는다. 따라서, mergesort를 재귀호출할 때마다 얼마만큼의 추가적인 저장장소가 만들어져야 하는지를 계산해 보면 된다. 처음 S의 크기가 n이면, 추가적으로 필요한 U와 V의 저장장소 크기의 합은 n이 된다. 다음 재귀 호출에는 n/2, 그 다음에는 n/4 등으로 추가적인 저장장소가 필요하다. 이들 저장장소의 크기를 합하면, 이 된다. 이 분석이 맞는 분석일까?...

28 합병정렬: 공간 복잡도 (2/3) n개 n개 lgn +1 번 n개 n개 = n(lgn +1) 의 저장장소 필요

29 합병정렬: 공간 복잡도 (3/3)

30 합병정렬: 공간 복잡도 향상 알고리즘 (1/4) 문제: n개의 정수를 (비내림차순으로) 정렬하시오.
입력: (1) 크기가 n인 배열 S[1..n]  전역적으로 정의 (2) low - 배열의 첫번째 인덱스, high – 배열의 마지막 인덱스 출력: (비내림차순으로) 정렬된 배열 S[1..n] 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);

31 합병정렬: 공간 복잡도 향상 알고리즘 (2/4) mergesort2(1,8) mergesort2(1,4)

32 합병정렬: 공간 복잡도 향상 알고리즘 (3/4) 합병(merge2)
문제: 두 개의 정렬된 부분배열을 하나의 정렬된 배열로 합병하시오. 입력: (1) 전역적으로 선언되어 있는 부분 배열 S[low..high] (단, S[low..mid]와 S[mid+1..high]는 이미 각각 정렬이 완료됨) (2) 첨자 low, mid, high 출력: 정렬이 완료된 부분배열 S[low..high]

33 합병정렬: 공간 복잡도 향상 알고리즘 (4/4) void merge2(index low, index mid, index high){ index i, j, k; keytype[] U = new keytype[low..high]; 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]; 이 알고리즘이 정말 공간 복잡도를 향상 시키는가?

34 합병정렬: 공간 복잡도 향상 알고리즘 (4/4) keytype[] U = new keytype[1..n];
void main() { … mergesort2(1,n) … } void mergesort2 (index low, index high){ … merge2(…) … } 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];

35 The Master Theorem (1/4) Proof of the theorem is …. omitted.
[부록 B]의 p.564, 정리 B.5 Consider a function f(n) that, for all n=bk for all kZ+, satisfies the recurrence relation: (n=bk 일 때, 다음 점화 관계가 성립하면) f(n) = af(n/b) + cnd with a≥1, integer b>1, real c>0, d≥0. Then: Proof of the theorem is …. omitted.

36 The Master Theorem (2/4)

37 The Master Theorem (3/4)

38 The Master Theorem (4/4)

39 [부록 B] P.562

40 [부록 B] P.562

41 [부록 B] P.562

42 [실습 3] 합병 정렬 합병 정렬에 대한 [알고리즘 2.2., 2.3]과 제자리정렬(In-place) 기법인 [알고리즘 2.4, 2.5]를 Java 프로그램으로 작성해보자. SortMain.java 를 분석하기 완성되지 않은 다음 네 함수를 작성한다. public static long mergeSort(int n, int[] s) public static void merge(int h, int m, int[] u, int[] v, int[] s) public static void inPlaceMergeSort(int low, int high) public static void inPlaceMerge(int low, int mid, int high) num 값을 키워가며 각 방법에 대한 수행 시간을 비교한다. 단계별로 num 값을 증가시키면서 수행 시간을 비교해보자. 공간 복잡도를 좋게 만드는 것이 수행시간에도 영향을 미치는가? 그 정도는?