자료구조&알고리즘_동적계획법

Woogie·2022년 11월 1일
0

동적계획법

  • 해결한 작은 문제로 큰 문제를 해결하는 방식
  • Dynamic Programming(DP)라고도 부른다.
  • 메모리를 사용하는 대신 빠른 성능을 자랑한다.
  • 두 가지 방법론
    • 메모이제이션
    • 타뷸레이션

메모이제이션

  • 하향식 접근법
  • 동적 계획법에서 작은 문제들의 결과는 항상 같다.
  • 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다.

타뷸레이션

  • 상향식 접근법
  • 필요한 값들을 미리 계산
    (메모이제이션은 필요할때 계산, 타뷸레이션은 미리 계산)

동적계획법 문제 접근방법

키워드만으로 동적 계획법 문제임을 알기가 어렵다.
문제 유형을 알 수 없다면 아래 두가지를 확인해보자.

  • 가장 작은 문제를 정의할 수 있는가?
  • 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙성이 있는가?

위 두가지가 가능하다면 동적계획법 문제일 확률이 크다.

동적계획법 문제

백준 계단오르기

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스

profile
FrontEnd Developer

0개의 댓글