동적계획법1 Dynamic programming 동적 계획법 정리 동적 계획법의 개념은 문제에서 주어진 최종적인 결괏값을 만드는 것을 여러 개로 쪼개어 그 아랫단계로 만들어 내는 것이다. 즉 i번째의 결과를 도출해내기 위하여 i-1번째를 보고 i-1번째를 만들기 위하여 i-2번째를 참조하는 식이다. 다만 이런 예시는 단순히 반복문만으로 하드코딩을 하더라도 풀어낼 수 있다. 하지만 만약 i번째의 결과를 만들기 위하여 3가지 경우의 수가 존재한다면? DP[i] = DP[i-1] + DP[i-2] DP[i] = DP[i-2] + DP[i-3] DP[i] = DP[i-1] + DP[i-3] 와 같은 점화식이 나오고 그중에서 최댓값 혹은 최솟값을 구해야 한다면 반복문으로는 풀 수 없는 한계점에 이르게 된다. 단순히 3가지의 경우만 있더라도 10번째 최솟값을 구하기 위해선 3^1.. 2021. 4. 21. 이전 1 다음
냄비