[알고리즘] 분할정복(divide and conquer)

분할정복이란 ?

분할정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다. 대표적인 예로는 정렬 알고리즘 중 퀵 정렬이나 합병 정렬과 이진 탐색, 선택 문제, 고리 푸리의 변환(FTT) 문제들이 대표적입니다.

 

정렬 알고리즘

선택 정렬과 삽입 정렬의 최대 실행시간은 O(n^2)로 입력하는 배열의 크기가 크다면 정렬하는데 시간이 오래 걸릴 수 있습니다.

반면 분할정복 알고리즘을 사용하는 합병정렬의 실행시간은 O(nlogn)으로 퀵 정렬은 최대 O(n^2)지만 최선이나 평균의 경우 O(nlogn)으로 비교적 빠른 시간을 갖는 것을 볼 수 있습니다.

 

정렬 알고리즘	최대 실행 시간	최소 실행 시간	평균 실행 시간
선택 정렬	O(n^2)	O(n^2)	O(n^2)
삽입 정렬	O(n^2)	O(n)	O(n^2)
합병 정렬	O(nlogn)	O(nlogn)	O(nlogn)
퀵 정렬	O(n^2)	O(nlogn)	O(nlogn)

나중에 정렬만 다시 정리해서 올리도록 하겠습니다 . . !

 

분할정복 과정

1) Divide

    원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때까지 나눕니다.

 

2) Conquer

     각 하위 문제를 재귀적으로 해결합니다.
     하위 문제의 규모를 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결합니다.

 

3) Combine

     Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결합니다.

 

• Divide를 제대로 나누면 Conquer 과정이 쉬워지므로 Divide를 잘 설계하는 것이 중요
• 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데 이 부분에서 분할정복 알고리즘의 효율성 낮아질 가능성 존재

분할정복 특징

• 분할된 작은 문제는 원래 문제와 성격이 동일하고 입력 크기만 감소
• 분할된 문제는 서로 독립적이므로 순환적 분할 및 결과 결합이 가능

장점	단점
Top-down 재귀방식으로 구현하기 때문에 코드가 직관적 문제를 나누어 해결한다는 특징상 병렬적으로 문제 해결 가능	재귀 함수 호출로 오버헤드 발생 가능 스택에 다량의 데이터가 보관되는 경우 오버플로우 발생 가능

합병 정렬

합병 정렬이란 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법입니다.

합병 정렬 과정

1) Divide

    입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다.

 

2) Conquer

    부분 배열을 정렬합니다.

    부분 배열의 크기가 충분히 작지 않으면 (left < right) 순환 호출을 이용하여 다시 분할 정복 방법을 이용합니다.

 

3) Combine

    정렬된 부분 배열들을 하나의 배열에 합병합니다.

퀵 정렬

퀵 정렬이란 특정 원소 피봇(pivot)을 기준으로 주어진 배열을 두 부분 배열로 분할하고 각 부분 배열에 대해 퀵 정렬을 순환적으로 적용하는 방식입니다.

퀵 정렬 과정

1) Divide

    피봇 하나를 선택하여 피봇을 기준으로 두 개의 부분 배열로 분할합니다.

 

2) Conquer

    피봇을 기준으로 피봇보다 큰 값 혹은 작은 값을 찾습니다.

    왼쪽부터 피봇보다 큰 값을 찾고 오른쪽부터 피봇보다 작은 값을 찾아 두 원소를 교환합니다.

    분할된 부분 배열의 크기가 0이나 1이 될 때까지 반복합니다.

 

3) Combine

    conquer 과정에서 값의 위치가 바뀌므로 따로 결합은 하지 않습니다.

이진 탐색

이진 탐색은 정렬된 데이터를 효과적으로 탐색할 수 있는 방법으로 정렬된 데이터만 사용가능합니다.

이진 탐색 과정

1) Divide

    배열의 가운데 원소를 기준으로 왼쪽, 오른쪽 부분배열로 분할합니다.

    탐색키와 가운데 원소가 같으면 분할을 종료합니다.

 

2) Conquer

    탐색키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을 순환 호출하고, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 호출합니다.    

 

3) Combine

    탐색 결과가 직접 반환되므로 결합이 불필요합니다.

 

---

참고

https://loosie.tistory.com/237