피보나치수열 (1) 썸네일형 리스트형 동적계획법(memoization) 동적계획법이란(Dynamic Programming)? 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 분할 정복의 알고리즘과 비슷하지만 동적계획법의 각 부분 문제들은 다른 답을 구하는 이용될 수 있기 때문에 계산결과를 재활용함으로써 속도의 향상을 꾀한다. 부분 문제들의 답을 재활용한다는 말이 무슨 말일까? 피보나치 수열 문제로 예를 들어보자! 동적계획법을 이용한 피보나치 수열의 풀이 https://www.acmicpc.net/problem/2748 피보나치 수열은 다들 아는 것처럼 Fn = Fn-1 + Fn-2 (n>=2)의 점화식을 가지고 전개되는 수열이다. 0 1 1 2 3 5 8 13 21 34 ..... n번째 피보나치 수.. 이전 1 다음
