동적계획법
- 해결한 작은 문제로 큰 문제를 해결하는 방식
- Dynamic Programming(DP)라고도 부른다.
- 메모리를 사용하는 대신 빠른 성능을 자랑한다.
- 두 가지 방법론
메모이제이션
- 하향식 접근법
- 동적 계획법에서 작은 문제들의 결과는 항상 같다.
- 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다.
타뷸레이션
- 상향식 접근법
- 필요한 값들을 미리 계산
(메모이제이션은 필요할때 계산, 타뷸레이션은 미리 계산)
동적계획법 문제 접근방법
키워드만으로 동적 계획법 문제임을 알기가 어렵다.
문제 유형을 알 수 없다면 아래 두가지를 확인해보자.
- 가장 작은 문제를 정의할 수 있는가?
- 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙성이 있는가?
위 두가지가 가능하다면 동적계획법 문제일 확률이 크다.
동적계획법 문제
백준 계단오르기
출처
프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.
프로그래머스 데브코스