알고리즘> 피보나치

1. 재귀적 풀이법

엄청나게 간단하지만 단점은 수가 크면 클수록 시간 복잡도가 엄청나게 증가한다. 

이 알고리즘의 원리는 원래 문제를 해결하기 위해서 작은 문제를 푸는 방식이다.

부분 문제(subproblem) 푸는 방식이자 재귀 풀이법이다.

문제는 작은 값을 만나기까지 계속 쪼개지면서 너무나도 부분 문제가 중복된다는 점이다.

위 그림을 보더라도 F(n-3)이 4번 나온다.

 

 

 

2. 동적 풀이법

각 부분문제를 해결할 때마다 그것을 저장하고 필요할 때마다 가져다 쓰면 되는 것

즉 동적 프로그래밍 성격이다.