봉황대 in CS

정렬 알고리즘들에 대하여 알아보던 중, 합병 정렬(merge sort)과 퀵 정렬(quick sort)이 분할 정복 알고리즘 중 하나임을 깨닫고 먼저 분할 정복에 대해 정리하기 위하여 이 글을 작성한다. 분할 정복 (Divide-and-Conquer) '쪼개서 풀고 합하기' : 문제를 잘게 쪼개는 분할(Divide) + 문제를 풀어서 합하는 정복(Conquer) 분할 정복이란, 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다. 즉, 문제를 작은 2개의 문제로 분리한 후 각각을 해결한 다음, 그 결과들을 모아서 원래의 문제를 해결하는 전략을 말한다. (Top-down, 하향식 접근법) 조건 1. 문제를 쪼개 나가는 과정에서, 큰 문제와 작은 문제의 구조가 동일하거나 비슷해야 한다. =..