태코놀로지

첫 번째 문제에 이어서 선택한 문제는 백준 온라인 저지의 1149번 문제가 되겠다. 이웃과 서로 다른 색깔의 페인트로 집을 칠할 때, 가능한 초소의 비용을 찾는 문제다. 색은 R, G, B로 한정되어 있으며, 집의 수는 사용자의 입력으로 결정된다. 예를 들면, 아래와 같은 경우를 생각해볼 수 있다. R G B집1| 26 40 83집2| 49 60 57집3| 13 89 99 이 경우의 최소의 값은 (집1-R, 집2-B, 집3-R)로 색칠하는 방법으로 최소비용 96이 답안이 된다. 그리디 알고리즘이나 다른 방법을 통해서도 문제를 풀 수 있겠지만, Overlapping SubProblem 구조와 Optimal Substructure 특징이 두드러지는 문제이므로 다이나믹 프로그래밍을 활용하면 쉽게 해결할 수 있..

이전 게시글에서 다이나믹 프로그래밍에 대한 전반적인 정리를 진행했다. 이제부터는 정리한 내용을 바탕으로 쉬운 문제부터 조금 난이도가 있는 문제까지 다이나믹 프로그래밍 방법을 활용해서 풀어보고, 그 과정을 정리해본다. 첫 번째로 선택한 문제는 백준 온라인 저지의 1932번 문제이자, 프로젝트 오일러의 18번, 67번 문제가 되겠다. 세 문제는 동일한 문제로 삼각형의 하단을 따라 내려가면서 합이 최대가 되는 수를 찾는 문제다. 삼각형의 크기가 커짐에 따라서 경우의 수가 기하급수적으로 늘어나므로 다이나믹 프로그래밍을 통해 해결하는 것이 바람직하다. 특히 프로젝트 오일러의 67번 문제의 경우 상당히 빠른 연산을 통하더라도 산술적으로 200억년의 시간이 소요된다고 한다. 이에 반해 효율적인 다이나믹 프로그래밍을 ..