분할 정복

분할 정복

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산

일반적인 재귀 호출과 다른 점
문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눈다.

분할 정복을 사용하는 알고리즘의 세 가지 구성 요소

• 문제를 더 작은 문제로 분할하는 과정 (divide)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge)
• 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)

분할 정복의 장점
빠르다.

TODO
스트라센(Strassen)의 행렬 곱 알고리즘 찾아보기
분할 정복을 사용하는 알고리즘

같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다.
여러 번 중복되어 계산되는 부분 문제들이 있으면 효율 저하를 야기함
overlapping subproblems
동적 계획법이 고안된 계기가 됨