코딩하는 신학생의 넋두리

본 포스팅은 《구종만, 『알고리즘 문제 해결 전략』, 인사이트》 를 참고하여 만들어졌습니다. 7.1 도입 분할 정복(Divede & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해낸다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것에 있다. 분할 정복 알고리즘은 다음과 같은 세 가지 구성 요소를 가지고 있다. Divide : 문제를 더 작은 문제로 분할하는 과정 Merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 Base Case : ..