분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말합니다.
분할 정복은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 냅니다. 대표적인 분할 정복 알고리즘으로는 병합 정렬을 예로 들 수 있습니다.
분할 정복은 말 그대로 문제를 '분할'해서 '정복'한 다음 정답을 '조합'해 나간다는 의미를 지닙니다. 분할 정복은 재귀를 활용하는 대표적인 알고리즘입니다.
function F(x):
if F(x)가 간단 then:
return F(x)를 계산한 값
else:
x 를 x1, x2로 분할
F(x1)과 F(x2)를 호출
return F(x1), F(x2)로 F(x)를 구한 값
출처: 📚 파이썬 알고리즘 인터뷰
개발자로서 성장하는 데 큰 도움이 된 글이었습니다. 감사합니다.