최근 분할정복 문제를 풀어보고 있는데, 분명 풀었음에도 제가 이걸 분할정복으로 푼건지 긴가민가 하더라고요. 분할정복을 예전에 합병정렬 배울 때 처음 들어보았어서, 뭔가 분할정복은 주어진 문제를 나누어 풀고 그 결과를 다시 합하는 방식이여야 한다 생각했거든요.


근데 생각해보니 불현듯 느껴진게, 그건 분할정복이 아니라 분할정복의 한 구체적인 사례인 것 같았습니다. 분할정복은 더욱 일반적인 방법론으로서, 주어진 문제로부터 더욱 간단한 문제들을 얻어내 그 문제들을 푸는 것으로 기존 문제의 답을 얻어내는 것이란 생각이 들었습니다.


그러한 분할정복은, 합병정렬처럼 정렬하고자 하는 배열을 분할하여 그리 얻은 작은 배열들을 정렬한 후 그를 다시 병합하는 방식으로 해낼수도, 혹은 하나의 탐색공간을 한 개 이상의 더욱 작은 탐색공간들로 분할하여 그리 얻어낸 탐색공간들을 개별적으로 탐색하는 것으로 언제나 정답을 얻을 수 있음을 입증하여 해낼수도, 혹은 그 외 여러 다양한 방법으로도 해낼 수 있는 것 같습니다.


방금 든 생각을 한 번 적어보았습니다.