목록피보나치 (1)

퉁탕퉁탕 만들어보자

Dynamic programming [1] - 피보나치 수열

동적프로그래밍은 간단하게 생각하면, 이전에 도출된 해를 가지고 그 다음 해를 구하는 식으로 푸는것이다. 그러면 이게 문제를 점화식으로 나타낼 수 있는데, 점화식만 도출해 내면 코드는 아주 짧다. 가장 유명하고 쉬운 문제는 피보나치 수열이다. 피보나치 수열은, 처음 두 값이 주어진다. 수열의 n번째 값을 F(n) 이라고 할 때, F(0) = 0, F(1) = 1 이 주어진다. 그 다음으로 오는 수는 바로 이전 두 값의 합이다. F(0) = 0, F(1) = 1 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(2) + F(1) = 1 + 1 = 2 F(4) = F(3) + F(2) = 2 + 1 = 3 ... [0,1, 1, 2, 3, 5, .... ] 이렇게 나가게 되며, 점화식으로..
Computer/알고리즘 2022. 3. 30. 20:54
이전 Prev 1 Next 다음