분할 정복 (Divide-and-Conquer)

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

1 분할 정복 (Divide-and-Conquer)

2 분할정복식 설계 분할(Divide) 정복(Conquer) 통합(Combine) 하향식(top-down)
해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다. 정복(Conquer) 나눈 작은 문제를 각각 해결한다. 통합(Combine) (필요하다면) 해결된 해답을 모은다. 하향식(top-down) 이분 검색 피보나찌

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

4 의사 코드 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);

5 토의 입력: n,x,S 재귀 형식 파라미터? 꼬리 재귀(tail-recursion) 반복 알고리즘과 비교
void binsearch(…) { index low, high, mid; low = 1; high = n; location = 0; while (low <= high && location == 0) { mid = (low + high) / 2; if (x == S[mid]) location = mid; else if (x < S[mid]) high = mid - 1; else low = mid + 1; }

6 재귀 vs. 반복 반복형이 재귀형보다 빠르다. 재귀 반복
재귀형는 함수 호출이 재귀적으로 이루어지지만 반복형은 이를 피할 수 있다. 하지만, 계산 복잡도상의 큰 이득은 없다. 재귀 반복

7 이분검색 – 최악의 경우 분석 단위연산: x와 S[mid]의 비교
몇 번? 입력 크기: 배열의 크기 n (= high - low + 1)

8 최악의 경우 경우 1: 반쪽 배열의 크기가 정확하게 n/2이 될 때 최악의 경우 재현식(recurrence equation)

9 최악의 경우 경우 2: n이 2의 거듭제곱으로 제한되지 않았을 때 (과제)증명: 수학적 귀납법 이용

10 합병정렬(Mergesort) 분할 정복법 절차
쌍방 합병(two-way merging): 같은 순으로 정렬되어 있는 두 개의 배열을 정렬된 하나의 배열로 만드는 과정 합병을 반복적으로 적용하여 배열을 정렬 절차 분할: 배열을 n/2개의 요소로 구성된 2개의 부분배열로 분할 정복: 부분배열 정렬 통합: 정렬된 각 부분배열을 하나의 정렬된 배열로 합병

11 합병정렬 문제: n개의 정수를 비내림차순으로 정렬하시오. 입력: 정수 n, 크기가 n인 배열 S[1..n]
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); }

12 합병(Merge) 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병
merge(h,m,U,V,S); 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병 입력: (1) 양의 정수 h, m (2) 정렬된 배열 U[1..h], V[1..m] 출력: U와 V에 있는 키들을 하나의 배열에 정렬한 S[1..h+m] void merge(h, m, U[], V[], 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]; 표 2.1

13 합병 알고리즘: 최악의 경우 시간복잡도 분석 단위연산: U[i]와 V[j]의 비교 입력크기: h + m 분석: 최악의 경우
merge(h,m,U,V,S); 합병 알고리즘: 최악의 경우 시간복잡도 분석 단위연산: U[i]와 V[j]의 비교 입력크기: h + m 분석: 최악의 경우

14 합병정렬 알고리즘: 최악의 경우 시간복잡도 분석
mergesort (int n, keytype S[]) 합병정렬 알고리즘: 최악의 경우 시간복잡도 분석 단위 연산: merge에서 일어나는 비교 연산 입력 크기: n 배열 S의 크기 분석: 과제:

15 합병정렬 알고리즘: 최악의 경우 시간복잡도 분석
mergesort (int n, keytype S[]) 합병정렬 알고리즘: 최악의 경우 시간복잡도 분석 단위 연산: merge에서 일어나는 비교 연산 입력 크기: n 배열 S의 크기 분석:

16 토의 공간 복잡도 얼마만큼의 저장장소가 필요할까? Cf) 제자리 정렬(in-place sort) 알고리즘
공간 복잡도 향상을 위한 알고리즘

17 공간 복잡도가 향상된 알고리즘 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); }

18 merge2(low, mid, high); 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하시오.
입력: (1) 첨자 low, mid, high, (2) 부분 배열 S[low..high], 여기서 S[low..mid]와 S[mid+1..high]는 이미 각각 정렬이 완료되어 있음. 출력: 정렬이 완료된 부분배열 S[low..high]

19 merge2(low, mid, high); void merge2(index low, index mid, index high) { index i, j, k; U[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) move S[j] through S[high] to U[k] through U[high]; else move S[i] through S[mid] to U[k] through U[high]; move U[low] through U[high] to S[low] through S[high]; }

20 빠른정렬(Quicksort) 1962년 호아 정말로 빠른 정렬 일까? 분할교환정렬(Partition exchange sort)

21 빠른정렬 알고리즘 void quicksort (index low, index high) { index pivotpoint;
if (high > low) { partition(low, high, pivotpoint); quicksort(low, pivotpoint-1); quicksort(pivotpoint+1, high); }

22 분할 알고리즘: partition(low, high, pivotpoint);
문제: 빠른정렬을 위해 배열 S를 분할하라. 입력: 색인 low와 high,부분배열 S[low..high] 출력: 부분배열 S의 pivotPoint 색인 void partition (index low, index high, index& pivotpoint) { index i, j; keytype pivotitem; pivotitem = S[low]; //choose first item for pivotitem 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]; //put pivotitem at pivotpoint

23

24 분할 알고리즘 분석 모든 경우를 고려한 시간복잡도 분석 단위연산: S[i] < pivotitem
입력크기: n = high - low + 1 분석: T(n) = n - 1

25 빠른 정렬 알고리즘 분석 최악의 경우 가장 최악은? 정렬되어 있는 경우

26 빠른 정렬 알고리즘 최악의 경우 증명 모든 정수 n에 대해서, 임을 증명하시오. 증명:(수학적 귀납법) 귀납 출발점:
귀납 가정: 귀납 단계: 과제: why?

27 빠른 정렬 알고리즘 평균의 경우 분석

28

29 행렬 곱셈(Matrix Multiplication)
문제: nxn 행렬 곱 입력: 양수 n, nxn 크기의 행렬 A,B 출력: C = AB 알고리즘 void matrixmult (int n, const number A[][], const number B[][],number C[][]) { index i, j, k; 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][j] + A[i][k] * B[k][j]; }

30 Strassen의 행렬 곱셈 알고리즘(2x2)
단순방법: 곱셈 ? 덧셈 ? Strassen: 곱셈 ? 덧셈 ?

31 nxn 일때 n이 2의 거듭제곱일 때,

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

33 시간 복잡도 분석 단위연산: 곱셈 입력크기: n 임계값: 1

34 시간 복잡도 분석 단위연산: 덧셈/뺄셈 입력크기: n 임계값: 1

35 토의 n이 2의 거듭제곱이 아니면? 얼마나 빨라졌는가?

36 분할정복을 피해야 하는 경우 크기가 n인 입력이 2개 이상의 조각으로 분할되며, 분할된 부분들의 크기가 거의 n에 가깝게되는 경우 ⇒시간복잡도: 지수(exponential) 시간 크기가 n인 입력이 거의 n개의 조각으로 분할되며, 분할된 부분의 크기가 n/c인 경우. 여기서c는 상수이다. ⇒ 시간복잡도: