Dynamic Programming

Dynamic Programming  한국어로는 동적계획법이라 하며 Divide & Conquer와 같은 패러다임의 일종이다.예를 들어보면 다음과 같다.이 계단을 다 오르기 전 단계는 무조건 3가지 경우중 하나가 된다.얼핏보면 다음과 같이 재귀트리를 표현할 수 있다.얼핏보면 Divide & Conquer과 비슷하다.실제로 접근법 자체는 크게 다르지 않다.이후 더 깊이 재귀 절차를 보면 다음과 같다. 여기서 DP의 핵심은 반복되는 요소들이다.ways(n-2)는 2번 반복되는데 둘다 동일한 값이고 나머지 요소도 그렇다.즉,DP의 핵심은 이러한 반복되는 요소들을 저장해놓고 다시 계산하지 않고 불러서 사용하는 것 이다.중복되는 값을 저장하고 사용함으로써 선형 시간 복잡도를 갖는다.만일 저 문제를 DP로 해결하지..

2024.10.17