코테 알고리즘 다이나믹 프로그래밍 간단 이해 다이나믹 프로그래밍(dp)는 뭘까? 다이나믹 프로그래밍은 이름은 뭔가 거창하지만 개념은 간단한데 바로 최종 결과를 얻기 위해 필요한 하위 데이터를 계속 저장해서 상위 문제를 해결하는 방법이다 핵심은 하위 데이터를 계속 저장한다는 점이다 물론 이 말만 듣는다고 바로 이해하기는 어렵다 이해를 위해 예를 하나 들어보겠다 다이나믹 프로그래밍하면 무조건 따라오는 문제인 피보나치 수열을 보자 피보나치 수열은 n번째 수가 n-1과 n-2의 합인 수열이다 즉 n번째 수를 구하기 위해서는 n-1과 n-2의 정보가 필요하다 피보나치 수열을 다이나믹 프로그래밍으로 구하는 방법은 몹시 간단한데 코드는 다음과 같다 dp = [0]*n dp[0] = 1 dp[1] = 1 for i in range(2,n) : dp[i] = dp.. 2023. 11. 4. 이전 1 다음