피보나치수열 - 메모이제이션(동적계획법)

프로그래밍 응용 피보나치수열 - 메모이제이션(동적계획법) jangThang 2016. 8. 17. 8:50 이웃추가 본문 기타 기능 1 - 1 - 2 - 3 - 5 - 8 - 13 - 21 - 34 . . . . . 어떤 규칙으로 나아가고 있는 지 감이 오시나요? 너무나도 유명한 수열이라 이미 알고 계신 분들이 많을 거라 생각됩니다. 2(3항) = 1(1항) + 1(1항) 3(4항) = 1(2항) + 2(3항) 5(5항) = 2(3항) + 3(4항) . . . N항 = N-1항 + N-2항 이런 꼴로 나아가는 수열입니다.. 즉 전전항과 전항을 합한 것이 다음 항이 되는거죠. 이 수열을 메모이제이션 이라는 기법을 써서 구해봅시다. 백문이 불여일견 1. 기본코드 피보나치 수열은 갈수록 수가 엄청나게 커지기 때문에, long long 이라는 8byte짜리 큰 자료형을 썼습니다. 또한 메모이제이션 => 즉, 메모를 해서 중복되는 연산을 줄인다는 건데요. 메모를 하기위한 배열 Cache를 ...

원문링크 : 피보나치수열 - 메모이제이션(동적계획법)