'피보나치' 태그의 글 목록

저번 시간에는 그리디 알고리즘의 기초 문제를 다루어 보았습니다. 오늘은 피보나치 수열을 해 보도록 하겠습니다. 이 친구를 언급하기 전에, 일반항을 먼저 구해보도록 하겠습니다. 왜냐하면, 오늘 하는 내용과, 어느 정도 맞아 떨어지기 때문이에요. 먼저 피보나치 수열은 아래와 같은 관계식을 가집니다. a(0) = a(1) = 1 a(n) = a(n-1) + a(n-2) if n>=2 여기까지만 보면 크게 어려울 건 없어 보입니다. 그러면 어떻게 일반항을 구할까요? 2번째 식을 잘 변형해 봅시다. a(n) - a(n-1) - a(n-2) = 0 그러면 위와 같이 되는데요. 이를 (3)이라 합시다. 아래 꼴로 변형해 봅시다. 이걸 (4)라고 합시다. a(n) - ta(n-1) = k(a(n-1) - ta(n-2)..