동적계획법

동적계획법

문제를 여러 조각들로 나누고, 이 때 여러 번 계산되는 문제들을 메모리에 저장해서 속도를 올리는 개념

보통 경우의수, 확률, 이항계수 등에 사용한다.

Ø  재귀 호출: 문제를 여러 조각으로 쪼개 재귀적으로 해결하는 방법

Ø  완전 탐색: 재귀 호출을 이용해 최적화 문제 풀기

Ø  메모이제이션: 시간과 공간 트레이드오프로 동적 계획법 알고리즘 만들기

Ø  경우의 수 세기와 확률 문제 DP 로 풀기

 

★동적계획법 과정

①     모든 답을 만들어서 제일 좋은 답을 찾는 완전 탐색 알고리즘을 설계합니다.

②     부분 문제 정의에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다.

③     이를 위해 입력을 조작하거나 형태를 바꿔야 할 수도 있습니다.

④     재귀 호출은 이전의 선택과는 관련 없이 앞으로 남은 선택에 관련된 답만을 반환합니다.

⑤     메모이제이션을 적용합니다.

⑥     최적화하기

 

★경우의 수 계산하기

①     모든 답을 직접 만들어서 세어보는 완전 탐색 알고리즘을 설계합니다.

②     이 때 재귀호출의 각 단계에서 고르는 각 선택지에 다음과 같은 속성이 성립해야 합니다.

③     모든 경우는 이 선택지에 포함됨

④     어떤 경우도 두 개 이상의 선택지에 포함되지 않음

⑤     최적화 문제를 해결할 때처럼 이전 조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄입니다. 재귀 호출 함수는 앞으로 남아 있는 조각들을 채우는 경우의 수만을 반환해야 합니다.

⑥     메모이제이션을 적용합니다.

⑦     최적화하기

 

★k번째 답 계산하기

①     답들을 사전 순서대로 만들어가는 완전 탐색 알고리즘을 설계하고, 메모이제이션을 적용해 경우의 수를 세는 동적 계획법 알고리즘으로 바꿉니다.

②     각 선택지를 하나하나 고려하며, 이 선택지를 선택했을 때 만들어지는 답의 수 M 과 건너 뛰어야 할 답의 수 skip 을 비교합니다.

③     M≤skip: M 개의 답은 모두 우리가 원하는 답보다 앞에 있으므로, 이들을 건너뜁니다. skip=skip−M 이 됩니다.

④     Mgtskip: M 개의 답 중에 우리가 원하는 답이 있으므로, 이들을 선택합니다. M 개의 답 중에 skip 개를 건너뛴 것이 우리가 원하는 답입니다. 이 선택지를 답에 추가하고 재귀호출로 답의 나머지 부분을 만듭니다.

 

★계산 게임

①     상태가 주어질 때 이번 차례인 사람이 이기는지 반환하는 함수를 구성한다

a. 한번에 이길 수 있는 경우가 기저 사례

②     할 수 있는 모든 동작을 다 하고, 재귀호출한다.

a. 하나라도 상대가 지는 결과가 나오면 내가 이기고 , b. 전부 다 상대가 이기는 결과가 나오면 나는 진다

 

③     메모이제이션을 적용한다

★★메모이제이션(memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

[출처] 동적계획법|작성자 튜기