알고리즘> 피보나치
2021. 7. 26.
1. 재귀적 풀이법 엄청나게 간단하지만 단점은 수가 크면 클수록 시간 복잡도가 엄청나게 증가한다. 이 알고리즘의 원리는 원래 문제를 해결하기 위해서 작은 문제를 푸는 방식이다. 부분 문제(subproblem) 푸는 방식이자 재귀 풀이법이다. 문제는 작은 값을 만나기까지 계속 쪼개지면서 너무나도 부분 문제가 중복된다는 점이다. 위 그림을 보더라도 F(n-3)이 4번 나온다. 2. 동적 풀이법 각 부분문제를 해결할 때마다 그것을 저장하고 필요할 때마다 가져다 쓰면 되는 것 즉 동적 프로그래밍 성격이다.