03. 동적 계획법

[1. 개요]

큰 의미에서 분할 정복과 같은 접근 방식

그러나 하나의 문제의 답을 여러번 계산하는 대신 한 번만 계산하고

계산 결과를 재활용함

 

두 번 이상 계산되는 부분 문제를 중복되는 부분문제라고 한다.

 

계산의 중복 횟수는 분할의 깊이가 깊어질 수록 지수적을 증가한다.

(같은 값을 두번 이상 계산할 일이 빈번해질 수 있다.)

 

한 번 계산한 값을 저장해두었다가 재활용하는 최적화 기법을 메모이제이션이라 한다.

 

보통 동적 계획법 알고리즘 구현은 아래와 같은 두 단계로 구성

1. 문제를 완전 탐색을 이용해 해결
2. 중복되는 부분 문제를 한번만 계산하도록 메모이제이션을 적용

 

 

 

[2. 메모이제이션]

수학의 함수와 프로그래밍에서 함수는 사실 서로 다르다

프로그래밍을 할 때는 함수의 불변성이 성립하지 않을 수 있기 때문이다.

(전역 변수, 입력 파일... 과 같은 수 많은 입력에 의해 작동하기 때문.)

 

참조적 투명성

함수의 반환 값이 그 입력 값만으로 결정되는지의 여부

 

참조적 투명성 함수

입력이 고정되어 있을 때 그 결과가 항상 같은 함수

 

== 구현 패턴 (작성을 일관되게 하는 것이 좋다.) ==

1. 기저 사례를 제일 먼저 처리
   => 입력이 범위를 벗어난 경우 등...
   
   
2. cache[] 를 모두 -1로 초기화 
   => memset() 는 1byte 단위로 초기화 하기 때문
   => -1 은 아직 계산되지 않음을 의미
   => 반환 값이 음수일 수 있다면 무효함.
   
   
3. ret 값은 cache[a] 에 대한 참조형
   => cache 가 다차원배열일 때 유용하다.
   => 배열의 인덱싱 실수를 줄일 수 있다.
   
   

 

[3. 메모이제이션 시간복잡도]

(존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

=> 예시 (이항계수 계산)

=> 부분 문제의 수는 O(n^2)

=> 부분 문제를 계산 할 때 필요한 반복문은 없으니 O(1) 

=> 이항 계수를 동적 계획법으로 풀이 시 시간 복잡도 == O(n^2)

 

 

 

[4. 최적화 문제]

여러 개의 가능한 답 중 가장 좋은 답을 찾는 문제

 

최적화 문제에 특정 성질이 성립할 경우,

단순한 메모이제이션을 넘어

좀 더 효율적인 동적 계획법을 구현 할 수 있다.

 

최적 부분 구조

어떤 문제와 분할 방식에 성립하는 조건

각 부분 문제의 최적해만 있으면, 전체 문제의 최적해를 쉽게 얻어 낼 수 있는 경우

 

 

예시)

최대 증가 부분 수열

 

 

[5. 기타 예제들]

 

 

 

=> 완전탐색으로도 시간내에 풀린다함

=> 답안을 정렬해서 출력?