동적 계획법
복잡한 문제를 여러개의 간단한 문제로 분리, 간단한 문제들을 해결해 나가 결국 최종 답을 구하는 방법.
메모리를 적절히 사용해 수행 효
어떻게?
1. 큰 문제를 작은 문제로 나눈다. ( 이때 점화식을 세운다.)
2. 작은 문제들은 한번씩만 계산해 DP 테이블에 저장한다. -> 메모이제이션 기법
톱-다운 방식과 바텀-업 방식이 있다.
톱 - 다운 방식
재귀 함수 형태로 코드를 구현.
코드의 가독성이 좋고, 이해하기 편하다.
바텀 - 업 방식
가장 작은 부분부터 문제를 해결하면서 큰 문제로 확장.
반복문으로 구현한다.
대표 문제 : 피보나치 수열
D[N] = D[N - 1] + D[N - 2]
[참고]
주홍철, <면접을 위한 CS 전공지식 노트>, 길벗(2022), p51