Dynamic Programming
특별한 속성을 가진 복잡한 문제를 푸는 방법- 복잡한 문제를 그보다 단순한 하위 문제로 나눠서 풂
- 재귀적
- 가장 단순한 문제 + 1은 그 다음으로 단순한 문제
- 당연히 다 풀수는 없음
특별한 속성이 필요
- 메모이제이션
- 계산결과를 캐시에 저장한뒤 나중에 재사용하는 기법
처음 계산시 그 결과를 캐시에 저장- 깊은 재귀호출에 적합
- 이미 풀었던 하위(작은) 문제는 그냥 값을 가져오면 된다.
동적 계획법을 할때 메모이제이션을 사용한다.
- top-down 동적계획법
- bottom-up 동적계획법
- 가장 작은 문제부터 시작
- top-down보다는 빠름
- cpu 캐시에 친화적
- 재귀호출을 피할수있음
-
속도 향상은 공짜가 아님
- 동적 계획법을 적용할 수 있는 문제의 특징
- 최적부분 구조
- 예: 최단 경로 찾기
- 하위 문제의 최적 해법으로부터 큰 문제의 최적 해법을 구할 수 있음
- 동적 계획법과 그리디 알고리즘의 유용성 판단에 사용
- 하위 문제의 반복
- 예: 피보나치 수열
- 똑같은 평가를 반복해야 함
- 하위 문제의 크기가 작아야 함
- 최적부분 구조
- 분할 정복이랑 비슷한 거 같은디?
- 분할 정복:
- 큰 문제를 하위 문제로 나눔
- 하위 문제의 최적의 해법을 합침
반복되지 않는 하위 문제
- 동적 계획법:
- 큰 문제를 하위 문제로 나눔
- 하위 문제의 최적의 해법을 합침
반복되는 하위 문제
- 분할 정복:
- 동적 계획법으로 문제를 푸는 과정(가이드)
사용 가능한지 판단- 재귀
- 상태와 매개변수 결정
- 상태 간 관계 정립
- 종료조건 결정
- 메모이제이션 혹은 타뷸레이션 추가