분할정복 방법론

이번 포스팅은 알고리즘을 설계하는 방법 중 분할정복 방법에 대한 포스팅입니다.

 

분할정복이란 글자 그 자체로 이해하면 편합니다.

1. 분할 : Data를 분할한다.

2. 정복 : 분할된 Data에 알고리즘을 적용한다.

3. 결합 : 정복단계의 알고리즘 결과를 취합한다.

위 3단계를 거쳐서 알고리즘이 수행되는 단계를 거치는 알고리즘 설계기법입니다.

(단, 3단계 결합이 빠지는 경우도 분할정복 방법론으로 봅니다)

 

분할정복을 사용하는 알고리즘으로는 이진탐색, 퀵정렬, 합병정렬등을 예로 들 수 있습니다

 

이진 탐색을 예로 볼까요?

분할정복 방법론과 이진탐색 알고리즘 비교

 

 

위 이진탐색의 내용을 다시 보겠습니다.

 

정복에서 알고리즘이 종료되지 않는다면

 

분할 단계에서 받은 부분배열에서 또다시 부분배열을 나누게 됩니다.

 

원하는 수준으로 작은 Data가 나오기 전까지는 반복적으로 분할 - 정복이 반복되어야 합니다.

 

해당 알고리즘의 코드 구현을 위해서, 주로 함수의 순환호출을 통해서 구현을 하게됩니다.

(아니면 무한루프를 통해서 반복문을 실행하고, 조건문을 통해서 무한루프를 깨는 방법이 필요합니다)

teus-kiwiee.tistory.com/8?category=913859

Quick Sort