28장 : 알고리즘 개발 방법론 1 (Divide and Conquer, Dynamic Programming)

지금까지 살펴 본 알고리즘들은 주어진 문제를 최적으로 해결하는 것들이었습니다.  우리의 선조들이 힘든 연구와 통찰을 통해 찾아낸 아름답고도 멋진 해법들입니다.

하지만 이들은 처음 접한 문제들에 대해 어떻게 해법을 찾을 수 있었을까요? 또 우리가 새로운 문제를 접하게 될 때, 참조할 만한 비슷한 연구 결과가 없다면 어떻게 해결해야 할까요?

"알고리즘 개발 방법론"이라는 소제목으로 소개시켜드리고자 하는 네가지 접근법은 바로 이렇게 특별한 최적화된 해법이 없는 문제에 대해 어떻게 접근하여 최적화된 혹은 쓸만한 해법을 찾을 수 있는지에 대한 "방법론"을 살펴볼 것입니다.

대부분의 알고리즘 교과서들에서 이 방법론이 먼저 소개되고, 구체적인 문제로 들어가기 때문에 알고리즘을 공부하는데 큰 진입장벽이 되어왔던 영역입니다.  구체적인 걸 먼저 알아보고 일반적인 해법을 찾는 순으로 재배치해 보았는데, 효과가 있을런지 모르겠네요.

이번 장에서는 분할 점령(Divide and Conquer )와 동적 계획(Dynamic Programming)에 대해 알아보겠습니다.

강의 자료



강의 동영상

28.0 알고리즘 개발 방법론 1 - 시작 : 알고리즘 개발 방법론에서는 새로운 문제를 만났을 때 이에 대한 해법을 찾을 수 있는 기본 도구들에 대해 알아봅니다. 이 장에서는 분할 정복과 동적 계획법에 대해서 배웁니다.



28.1 분할 정복 (Divide and Conquer) 개념 : 분할 정복으로 문제를 푸는 것은 이미 여러번 소개된 바 있습니다. 분할 정복은 해결할 수 없는 큰 문제를 해결할 수 있는 수준까지 쪼개어 해결한 다음, 그 결과를 병합하여 가면서 최종적인 해답을 찾는 방법입니다.  재귀적인 구조이기 때문에 대부분 재귀 호출로 구현됩니다.  그리고 직관적이고 아름다운 해법입니다.



28.2 Strassen의 행렬 곱셈 : 분할 정복으로 문제를 푸는 예는 앞서 많이 소개 했습니다.  새로운 관점을 드리기 위해 행렬의 곱셈을 분할 정복으로 최적화하는 법을 알아 봅니다.  Strassen은 2x2 행렬의 곱셈에 대해 최적화된 계산법을 고안했는데, 이를 분할 점령법으로 응용하면 임의 차원의 정방 행렬에 대한 곱셈을 할 수 있습니다.



28.3 가장 가까운 쌍 (Closest Pair) : 공기가 좋은 곳에서 밤 하늘을 보면 엄청난 수의 별이 보입니다.  이 별들 중에서 가장 가까이 붙어있는 별을 찾을 수 있습니까? 가장 가깝다는 것은 가장 충돌할 가능성이 크다는 걸 의미하기 때문에 선박이나 비행기의 관제에서도 매우 중요한 문제입니다.  특히 매우 빨리 찾을 수 있어야 하므로 최적의 알고리즘이 필요합니다.  분할 점령법으로 가장 가까운 쌍을 효율적으로 찾아 봅니다.



28.4 동적 계획법 (Dynamic Programming) : 동적 계획법은 분할 점령과 연관되어 있습니다. 분할 점령은 문제를 작게 쪼개는데, 고로 작은 문제가 매우 많아집니다.  그런데 작은 문제들의 해는 중복될 가능성이 큽니다.  그렇다면 이미 풀이한 문제의 해를 따로 저장해 둔다면 중복된 문제는 계산하지 않고 찾아보는 것으로 효율을 높일 수 있습니다.  하지만 동적 계획법은 분할 점령하는 문제 모두에 적용될 수는 없습니다.



28.5 동적 계획법으로 Knapsack 문제 풀기 : 여러 개의 베낭(Knapsack)에 서로 다른 물건을 담는 Knapsack 문제는 매우 유명합니다. 실제 이 해법은 컨테이너에 화물을 어떻게 실어야 가장 이익을 볼 수 있는지를 찾는데 활용될 수 있습니다.  Knapsack문제는 조건에 따라 해법도 가지각색입니다. 여기에서는 Unbounded Knapsack 문제를 동적 계획법으로 푸는 방법을 알아봅니다.



28.6 외판원 순회 (Traveling Salesman) 문제 : 외판원 순회는 모든 정점이 연결된 그래프에서 모든 정점을 방문하고 원래 출발지로 돌아오는 최소비용의 경로를 구하는 문제입니다.  이 또한 실제 많이 제기되는 문제이지만 의외로 쉽게 풀 수 있는 해법은 찾아지지 않았습니다.



28.9 알고리즘 개발 방법론 1 - 결론 : 분할 점령과 동적 계획법에 대해서 살펴 보았고,  알고리즘 분야에서 유명한 문제들을 살펴보고 이를 풀이해 보았습니다.  더 흥미로운 내용은 다음 장에 이어집니다.

---

관련글 |
  - C++로 배우는 알고리즘
  - 27장 : 회귀와 스플라인 (Regression & Spline)
  - 29장 : 알고리즘 개발 방법론 2 (Greedy Method, Backtracking)