코딩테스트에서 DP 알고리즘은 단골 문제로 나온다. 그런데도 많은 사람들이 어려워하고, 나 또한 매우 어려워한다. 이번 기회에 개념을 확실히 다지고 DP 를 정복하고자 한다!! 피보나치 수열 DP 알고리즘의 대표적인 예시이다. 예시를 보면서 DP를 이해해보자. 피보나치 수열은 점화식으로 표현할 수 있다. 이 점화식을 따라서 알고리즘을 짜기 위해서는 재귀 함수를 이용해야한다. int fib(int n){ if (n==1 or n==2){ return 1; } return fib(n-1) + fib(n-2); } 그런데 이런식으로만 작성하면 구하고자 하는 값이 커질때는 시간이 너무 오래 걸릴 수도 있다는 한계점이 있다. 왜냐하면 이미 구한 값을 계속 구해야하기 때문이다. n이 1이거나 2일때가 나올때까지 계..
