dynamic programming

다이나믹프로그래밍(Dynamic Programming)

📔 다이나믹프로그래밍(Dynamic Programming)이란 하나의 문제는 단 한 번만 푸는 방법! 다이나믹프로그래밍 (이하 DP) 작은 문제를 해결하여 큰 문제를 해결하는 분할정복과 유사하다고 생각할 수 있지만, 분할정복의 경우 한번 풀었던 문제를 다시 푸는 비효율적인 단점을 가지고 있다. (일부 경우 제외 (병합정렬)) 분할정복과 DP의 차이를 보여주는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열: 바로 앞과 앞앞 두 칸의 숫자의 합을 구해서 나타내는 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 분할정복을 이용한다면 이미 구한 숫자들을 다시 계산하는 단점이 있다. 위의 사진을 보면 13을 구하는게 2번, 12 3번, 11 3번 계산하는 것을 볼 수 있다. 이런 문제를 ..