분할정복에 대해 설명하고 그 예시를 드시오

[tmfrlrkvlek]

[inuinseoul]

분할정복은 이름 그대로 문제를 분할하여 해결하는 방법입니다. 분할정복은 3단계로 구성됩니다.

• Divide : 문제를 나눔
• Conquer : 나눠진 문제를 각각 해결
• Combine : 해결한 문제의 답을 결합

이는 문제가 허락하는한 재귀적으로 적용할 수 있습니다. 예를 들어보겠습니다. 1부터 8까지의 숫자를 더하는 문제를 생각해봅시다. 이는 1~4를 더하는 문제와 5~8을 더하는 문제로 나누어 생각할 수 있습니다. 이렇게 나누어진 문제는 1~2,3~4 그리고 5~6,7~8을 더하는 문제로 나누어 생각할 수 있습니다. 마지막으로는 1~1,2~2,3~3,4~4,5~5,6~6,7~7,8~8을 더하는 문제로 생각할 수도 있습니다. 여기서부터는 더 나눌 수 없으므로 이제 문제를 해결하고 더하는 것을 반복해 원래 해결하려던 문제인 1~8의 합을 계산해냅니다.

[tmfrlrkvlek]

문제를 나눌 수 없을 때까지 나누어 풀고 다시 합병하여 문제의 답을 얻는 방식으로, 하향식 접근법입니다.
첫째로 현재의 문제와 동일하되 입력의 크기가 작은 다수의 부분 문제로 분할합니다.
둘째로 부분 문제를 재귀적으로 풀어서 정복합니다.
부분 문제의 크기가 충분히 작아 더 이상 재귀 호출을 할 수 없을 경우 직접적인 방법으로 풀이합니다. 이 경우 “재귀가 바닥을 쳤다(Bottoms out)” 혹은 “베이스 케이스(Base case)까지 내려왔다”라고 표현합니다.
셋째로 부분 문제의 해를 결합해 원래 문제의 해로 만듭니다.
위 과정을 통해 분할 정복으로 문제의 답을 얻을 수 있습니다.

[duyeonnn]

분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘이다.

분할 정복 알고리즘은 다음과 같은 단계를 거친다.

• Divide: 문제가 분할이 가능한 경우 2개 이상의 문제로 나눈다.
• Conquer: 나누어진 문제가 여전히 분할이 가능하면 다시 Divide를 수행하고 아니면 문제를 푼다.
• Combine: Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

문제를 제대로 나누면 Conquer하는 것은 쉽기 때문에 Divide를 제대로 하는 것이 중요하다.

분할정복의 예시로는 병합 정렬, 이진 탐색, FFT(Fast Fourier Transform) 알고리즘 등이 있다.

[sustainable-git]

• 분할 정복 Algorithm은 해결할 수 없는 문제를 작은 문제로 분할하려 해결한 후 합치는 형태로 진행됩니다. 주로 재귀 함수 형태로 구현이 됩니다.
• 대표적인 분할 정복은 Quick Sort와 Merge Sort가 있으며 하노이의 탑 문제가 있습니다.