[알고리즘] 분할정복 방법

[알고리즘] 분할정복 방법

 

-알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.

 

1. 분할 정복 방법(Divide-and-Conquer)

-분할 정복 방법은 순환적으로 문제를 푸는 하향식 접근 방법이다.

-주어진 문제의 입력을 더 나눌 수 없을 때까지 2개 이상의 작은 문제로 순환적 분할하고, 이들을 각각 해결한 뒤, 이들의 해를 결합해 문제의 답을 구하는 방식이다.

 

*분할 정복 방법의 단계

(1) 분할(Divide): 주어진 문제의 입력을 여러개의 작은 문제로 분할함

(2) 정복(Conquer): 작은 문제들을 순환적으로 분할함. 더이상 나눌 수 없다면 문제를 각각 푼다

(3) 결합(Combine): 여러개의 해들을 결합해 문제의 해를 구한다.

 

-분할 정복 방법의 핵심은 '문제를 잘게 쪼개는 것'이다.

-잘게 쪼개진 문제들은 원래 문제보다 입력 크기만 작을 뿐, 문제 자체는 동일하다.

-이들은 서로 독립적이기 때문에, 각각의 작은 문제를 다시 순환적으로 분할하고, 결과를 통합하는 것이 가능하다.

-ex: 퀵 정렬, 합병 정렬, 이진 탐색

 

 

2. 이진 탐색 문제

-A[]={10,15,20,25,30,25,40,45,50} 일때, 배열 A에서 탐색키 key=20의 이진 탐색 과정을 순환 알고리즘을 통해 설명해보자.

-> 이진 탐색 알고리즘을 분할 정복 방법에 적용시켜본다면

(1) 분할: 입력크기가 n인 배열을 가운데 원소 기준으로 크기가 n/2인 왼쪽 배열/오른쪽 배열로 나눈다. 

(2) 정복: 키가 가운데 원소보다 작으면 왼쪽, 크면 오른쪽 배열을 대상으로 이진 탐색을 순환 호출한다.

(3) 결합: 이진탐색의 결과가 직접 반환되기 때문에, 결과를 결합하는 과정은 필요가 없음!