반응형 Dynamic Programming2 기초적인 동적계획법(Dynamic Programming) 문제 풀기 다이나믹 프로그래밍은 문제를 많이 풀어봐야지 느낌이 오는 것 같다. 그래서 이 글에서는 가장 기초적인 1~2차원 다이나믹 프로그램을 활용해야하는 문제에 내가 했던 접근을 설명할 생각이다. 계단오르기 2579번 계단오르기 우선, 이 문제의 설명을 보면 다음과 같은 제약들이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 이 조건을 모두 만족시키는 경우 중에서도 최대의 값으로 가는 경우의 점수를 구해야한다. 다이나믹 프로그래밍에선 중요한 것은 다음과 같다. 이미 계산했던 값은 계산하.. 2016. 10. 14. 동적계획법(Dynamic Programming) 입문하기 DP(Dynamic Programming)? DP는 문제를 최적화를 할 때, 사용을 주로 합니다. 불필요하게 다시 계산을 하는 일을 막아 주는 기능을 합니다. 예를 들어, 가장 기본 적인 Fibonacci(피보나치) 숫자를 구하는 경우를 생각해 봅시다. 여기서 가장 단순하게 생각할 수 있는 코드는 피보나치는 f(n) = f(n-1) + f(n-2) 즉 n번째 피보나치 숫자는 n-1번 째 피보나치 수와 n-2번 째 피보나치 수의 합과 같다 입니다. 이를 재귀 함수로 나타내면 int nth_fibonacci(int n) { if(n 2016. 10. 13. 이전 1 다음 반응형