목록dp (1)

태코놀로지

DP 문제풀이 #1 - 숫자삼각형

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