8장 동적 계획법

neptunes032·2020년 9월 13일
0

종만북

목록 보기
1/6

8.1 도입

중복되는 부분 문제

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미합니다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로 부터 원래 문제에대한 답을 계산해 내기 때문입니다. 이 과정에서 어떤 부분 문제는 두개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러번 계산하는 대신 한번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있습니다.

키워드

  • cache
  • overlapping subproblems
  • memoization

메모이제이션을 적용할 수 있는 경우

  • 참조적 투명성(referential transparency)
    • 함수의 반환 값이 그 입력 값만으로 결정됨을 의미한다.

메모이제이션 구현 패턴

동적 계획법은 가장 흔한 문제 유형 중 하나이기 떄문에 메모이제이션은 굉장히 자주 구현하게 된다. 따라서 한 가지 패턴을 정해두고 항상 같은 형태로 구현하도록 하자.

  1. 항상 기저 사례를 제일 먼저 처리한다.
    • 기저 사례를 먼저 확인하고 chace에 접근하자.
  2. cache 초기화
    • memset()
      • 제한적 0 혹은 -1 로 초기화 가능하다.
  3. 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));
}

동적 계획법 레시피

  1. 주어진 문제를 완전 탐색을 이용해 해결합니다.
  2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용합니다.

다른 구현 방법에 대하여

  • 반복적 동적 계획법 9장에서 다룬다.

8.2 문제: 와일드카드(WILDCARD, 중)

  • 다시읽기

8.3 풀이: 와일드카드

중복되는 부분 문제

다른 분해 방법


8.4 전통적 최적화 문제들

동적 계획법의 가장 일반적인 사용처는 최적화 문제의 해결입니다. 최적화 문제란 여러 개의 가능한 잡 중 가장 좋은 답을 찾아내는 문제를 말합니다.최적화 문제를 동적 계획법으로 푸는 것 또한 완전 탐색에서 시작합니다만, 최적화 문제에 특정 성질이 성립할 경우에는 단순히 메모이제이션을 적용하기보다 좀더 효율적으로 동적 계획법을 구현할 수 있습니다.


예제: 삼각형 위의 최대 경로(TRIANGLEPATH, 하)


완전 탐색으로 시작하기

무식하세 메모이제이션 적용하기

입력 걸러내기

이론적 배경: 최적 부분 구조

profile
개발자가 되고싶다.

0개의 댓글