Computer Algorithms C++ Divide & Conquer 분할 정복

Computer Algorithms C++

Divide & Conquer

분할 정복

Divide & Conquer의 개념

• Divide & Conquer방법의 근본 원리는 주어진 문제에서 입력 의 크기가 큰 것을 다루는 것보다는 입력을 작은 크기로 분할 해서 해결하는 방법이다. 이 방법의 알고리즘은 다음과 같은 단계로 문제를 해결한다.

– 첫째, 입력을 더욱 작은 크기로 분할하고, – 둘째, 반복적으로 분할된 입력들을 해결하고,

– 셋째, 얻어진 부분 해들을 조합해서 원래의 입력에 대한 전체 해를 얻는다.

• 입력의 크기가 작은 경우에는 직접적으로 문제를 해결하고, 입력이 아직도 크다면 순환적으로 반복하여 분할한다.

Divide & Conquer의 개념

Type DAndC(P) {

if Small(P) return S(P);

else {

divide P into smaller instances P1, P2, ... , Pk , k≥1;

Apply DAndC to each of these subproblems;

return Combine(DAndC(P1) , DAndC(P2) , ... , DAndC(Pk));

} }

Program 3.1 Control abstraction for divide-and-conquer

Divide & Conquer의 개념

• 시간복잡도

– 여기서 T(n)은, 입력의 크기가 n인 문제에 대하여 DAndC를 적용 했을 경우의 알고리즘 수행시간이고, g(n)은 충분히 작은 입력 에 대하여 분할하지 않고 직접 계산할 경우의 시간을 의미한다.

그리고 f(n)은 P를 분할하는데 필요한 시간과 계산된 부분해들 을 결합하는 데 걸리는 시간이다.

Solving Recurrence Relations

• DAndC 알고리즘의 순환식

– T(1)은 입력 n이 충분히 작을 때, 더 이상 분할하지 않고 직접 계산할 경우의 계산시간.

– b는 입력 n을 몇 개의 부분으로 분할할 것인가를 결정하는 상수.

– a는 이런 분할된 부분 중에서 부분해를 계산하기 위해 몇 개를 더 고려 해야 하는가를 결정하는 상수(계산의 편의를 위해 n=b^k임을 가정한다.).

– 함수 f(n)은 전체해를 구하기 위해 부분해를 합치는데 걸리는 시간

Solving Recurrence Relations

• Example 3.1

a=2와 b=2인 경우를 생각해 보자. 여기서 T(1)=2이고 f(n)=n이라 고 하자.

또한, 위의 순환식에서 우변에 나타난 함수 T를 소거하기 위하여

i=log₂n를 대입(우변의 함수 T(n/2ⁱ)를 T(1)으로 나타낼 수 있으며, T(1) 은 이미 알고 있는 상수값(2)이다.)하여 다시 나타내면 다음과 같은 결 과를 얻을 수 있다.

일반화하면,

Binary Search

Binary Search

이진검색의 예

key = 4를 검색

i=0, l=11, mid=5 1 3 4 5 6 7 9 10 11 13 14 i=0, l=4, mid=2 1 3 4 5 6 7 9 10 11 13 14 i=0, l=2, mid=1 1 3 4 5 6 7 9 10 11 13 14 i=2, l=2, mid=2 (Found) key = 12를 검색

점화식

다른 검색 방법

Ternary Search

T(n) = T(n/3) + 2 (?)

Quartary Search

T(n) = T(n/3) + 3 (?)

Powering a number

피보나치 수

정리 : F_n+1 Fn 1 1 n F_n F_n-1 1 0

귀납법으로 증명

Finding the Maximum and Minimum

Finding the Maximum and Minimum

MinMax(1, n, x, y)

a: 1 2 3 4 5 6 7 8 9 22 13 -5 -8 15 60 17 31 47

1, 9, 60, -8

1, 5, 22, -8 6, 9, 60, 17

1,3,22,-5 4,5,15,-8 6,7,60,7 8,9,47,31 1,2,22,13 3,3,-5,-5

Finding the Maximum and Minimum

– n=2^k(n은 2의 승수)을 가정한다면 T(n)을 다음과 같이 구할 수 있다.

Merge Sort

Merge Sort

Merge Sort

• Example

• 입력리스트:[310,285,179,652,351,423,861,254,450,520]

Merge Sort

– n=2^k(n은 2의 승수)을 가정한다면 T(n)을 다음과 같이 구할 수 있다

Quick Sort

Quick Sort