8.1 도입
중복되는 부분 문제
동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미합니다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로 부터 원래 문제에대한 답을 계산해 내기 때문입니다. 이 과정에서 어떤 부분 문제는 두개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러번 계산하는 대신 한번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있습니다.
키워드
- cache
- overlapping subproblems
- memoization
메모이제이션을 적용할 수 있는 경우
- 참조적 투명성(referential transparency)
- 함수의 반환 값이 그 입력 값만으로 결정됨을 의미한다.
메모이제이션 구현 패턴
동적 계획법은 가장 흔한 문제 유형 중 하나이기 떄문에 메모이제이션은 굉장히 자주 구현하게 된다. 따라서 한 가지 패턴을 정해두고 항상 같은 형태로 구현하도록 하자.
- 항상 기저 사례를 제일 먼저 처리한다.
- 기저 사례를 먼저 확인하고 chace에 접근하자.
- cache 초기화
- memset()
- 제한적 0 혹은 -1 로 초기화 가능하다.
- memset()
- cache의 참조형을 반환
메모이제이션의 주먹구구식 시간 복잡도 분석
시간복잡도 = (존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)
예제: 외발 뛰기(JUMPGAME, 하)
재귀 호출에서 시작하기
int solve(int x, int y) {
if (x >= N || y >= N)
return 0;
if (x == N - 1 && y == N - 1)
return 1;
int distance = board[x][y];
return solve(x + distance, y) ||solve(x, y + distance);
}메모이제이션 적용하기
int solve(int x, int y) {
// 기저 사례를 처음에 처리한다.
if (x >= N || y >= N)
return 0;
if (x == N - 1 && y == N - 1)
return 1;
// cache 되어 있다면 곧장 반환한다.
int& ret = cache[x][y];
if (ret != -1) return ret;
// 여기서 답을 계산한다.
int distance = board[x][y];
return ret = (solve(x + distance, y) || solve(x, y + distance));
}동적 계획법 레시피
- 주어진 문제를 완전 탐색을 이용해 해결합니다.
- 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용합니다.
다른 구현 방법에 대하여
- 반복적 동적 계획법 9장에서 다룬다.
8.2 문제: 와일드카드(WILDCARD, 중)
- 다시읽기
8.3 풀이: 와일드카드
중복되는 부분 문제
다른 분해 방법
8.4 전통적 최적화 문제들
동적 계획법의 가장 일반적인 사용처는 최적화 문제의 해결입니다. 최적화 문제란 여러 개의 가능한 잡 중 가장 좋은 답을 찾아내는 문제를 말합니다.최적화 문제를 동적 계획법으로 푸는 것 또한 완전 탐색에서 시작합니다만, 최적화 문제에 특정 성질이 성립할 경우에는 단순히 메모이제이션을 적용하기보다 좀더 효율적으로 동적 계획법을 구현할 수 있습니다.
예제: 삼각형 위의 최대 경로(TRIANGLEPATH, 하)
완전 탐색으로 시작하기
무식하세 메모이제이션 적용하기
입력 걸러내기
이론적 배경: 최적 부분 구조
개발자가 되고싶다.