다이나믹 프로그래밍
큰 문제를 반복되는 작은 문제로 나누어 해결하는 방법
다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다.
1. 큰 문자를 반복되는 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
즉, 크고 어려운 문제가 있으면 먼저 잘게 나누어 해결한 뒤에 나중에 전체의 답을 구하는 것이다.
분할 정복 기법
과 유사하나, 메모이제이션 Memoization이 사용된다는 점에 분할 정복과 다르다. 분할 정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법인데, 이 작은 문제 간 반복이 없다는 특징이 있다.
반면 다이나믹 프로그래밍
은 반복되는 모든 작은 문제들을 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 메모하고, 다시 그보다 큰 문제를 풀 때 똑같은 작은 문제가 나타나면 앞서 메모해두었던 작은 문제의 결과값을 이용한다. 이를 메모이제이션 Memoization
이라고 한다.
BOJ 24416. (Bronze 1) 알고리즘 수업 - 피보나치 수 1
BOJ 11048. (Silver 2) 이동하기
https://blog.naver.com/ndb796/221233570962
https://galid1.tistory.com/507