분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer)

문제를 나눌 수 없을 때 까지 나눠 각각을 풀면서 다시 합병하여 문제를 해결하는 알고리즘이다.
상위의 해답을 구하기 위해 아래로 내려가며 하위의 해를 구하는 하향식 접근법을 사용하여 일반적으로 재귀함수로 구현된다.

분할정복의 대표적인 알고리즘은 퀵 정렬과 병합 정렬이 있다.

DP와 분할 정복이 비슷한 느낌이어서 공통점과 차이점을 찾아보았다.

 

• 공통점
  • 문제를 가장 작은 단위가 될 때까지 나눠서 분할함

 

•  차이점
  • 동적 계획법
    • 중복된 문제의 답은 저장되어 상위 문제 해결 시 재활용 됨 (메모이제이션 기법)
  • 분할 정복
    • 부분 문제는 서로 중복되지 않음(메모이제이션 기법 사용 안함)

분할 정복을 설계하는 방법

1) Divide : 문제가 분할이 가능할 경우, 2개 이상의 문제로 분할한다.
2) Conquer : 나눠진 문제가 여전히 분할이 가능하면 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.
3) Combine : Conquer한 문제들을 병합하여 원래 문제의 답을 얻는다.

분할 정복의 장단점

• 장점 : 문제를 나눔으로써 어려운 문제를 해결할 수 있다는 장점이 있다. 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 장점이 있다.
• 단점 : 일반적으로 재귀 함수를 사용하기 때문에 오버헤드가 발생하며, 스택에 많은 데이터를 저장하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 된다는 단점이 있다.

# 분할 정복 수도 코드
# 코드 출처: 박상길님의 ‘파이썬 알고리즘 인터뷰’ 책 
function F(x):
    if F(x)가 간단 then:
        return F(x)를 계산한 값 # 정복
    else:
        x를 x1, x2로 분할
        F(x1)과 F(x2) 호출 # 분할
        return F(x1), F(x2)로 구한 값 # 조합