분할 정복

분할 정복

문제를 나눌 수 없을 때까지 나눈 뒤, 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘.

 

분할 정복 설계 전략

1. 분할(Divide) 단계

- 문제를 같은 유형의 여러 개의 더 작은 부분 문제들로 나눈다.

- 부분 문제는 풀기 쉬울 때까지 계속 나눈다.

2. 정복(Conquer) 단계

- 부분 문제들을 보통 재귀적으로 해결하여 해를 구한다.

3. 합병(Merge) 단계

- 문제에 대한 해를 구하기 위해 부분 문제들의 해를 합친다.

 

-> 문제를 제대로 나눈다면 정복 단계는 쉬워지므로 분할 단계를 제대로 해야한다.

 

문제 : 최댓값 최솟값 찾기

문제: 크기가 n인 배열내의 요소들 중 최댓값과 최솟값을 찾는다.

<쉬운 전략>

1.최댓값을 찾는다.           -- 비교 횟수: n – 1

2.남은 배열 요소들의 최솟값을 찾는다. -- 비교 횟수: n – 2

  총 비교 횟수 = (n – 1) + (n – 2) = 2n - 3

 

<분할 정복 전략>

1. 배열을 반으로 나눈다.

2. 양쪽 절반들의 최댓값과 최솟값을 찾는다.

3. 2에서 찾은 두 개의 최댓값들과 두 개의 최솟값들을 비교하여 전체 배열의 최댓값과 최솟값을 구한다.

 

<분할 정복 알고리즘 진행 과정>

최댓값과 최솟값 찾기 알고리즘

<실행 트리>

 

다른 예시

data = {91, 82, 13, 85, 68, 70, 98, 24} 배열이 있다. 합병 정렬(오름차순)해보자.

 

전략

1. 배열을 반으로 나눈다.

2. 왼쪽 반과 오른쪽 반을 각각 정렬한다.

3. 정렬된 왼쪽 반과 오른쪽 반을 합병한다.

 

합병 정렬 진행 과정

합병 정렬 알고리즘

 

합병 정렬의 단점

- 입력을 위한 메모리 공간 (입력 배열)외에 추가로 입력과 같은 크기의 공간 (임시 배열)이 별도로 필요

- 2개의 정렬된 부분을 하나로 합병하기 위해 합병된 결과를 저장할 공간이 필요하기 때문