알고리즘 스터디 [DP] - 동적 계획법

창업을 멈추고 나서 개발적 고민 인생에 대한 고민을 하면서 앞으로 무엇을 할지에 대해 여러 기회들을 찾아보았는데 인턴 모집이 있어서 지원하려고 했다. 그러나 창업이 잘 될줄 알고 뒤를 준비 안했더니 알고리즘을 손에 놓고 있었다. 그래서 이번 알고리즘 스터디를 열심히 해서 11월 말이나 12월부터 인턴을 했으면 좋겠다.

동적계획법 (Dynamic Programming)

동적계획법은 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용할 수 있는 알고리즘 설계 기법이다. 주어진 문제를 풀기 위해 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다.

• 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아냄
• 단순한 재귀함수에 대입해 최적해를 구할 수 있지만 대다수는 훨씬 더 복잡한 프로그래밍을 요구함

탐욕법과의 비교

동적 계획법은 위에서 말했듯이, 가능한 ㅇ법은 모든 경우를 고려해 최적의 경로를 찾지만 탐욕법은 전체적인 상황보다는 순간순간에서의 가장 빠른 경로를 찾아준다.** 이 말은, 단기간에 효과를 얻을 수 있지만 항상 최적의 경로를 찾아주지 않아 전체적으로 최적의 경로가 되지 않는 경우가 있다.

최적해 구하기

동적계획법에서 핵심은 문제의 재귀적 구조를 발견해 작은 문제의 답을 이용해 원래의 답을 계산하는 것이다.

예시) 동전의 합
coins = {c1, c2, ..., ck}를 조합해 만들어야 하는 목표 액수 n이 있을 때 n 값을 구하기 위한 최적의 조합을 찾아라. 예를 들어, coins = {1, 2, 5} / n = 12일 경우 5 + 5 + 2 = 12를 구할 수 있다.

이러한 예시에서 우리가 최적해를 구할 때 x를 구하기 위한 동전의 최소 개수를 의미하는 함수를 solve(x)라고 하자 예를 들어, coins = {1, 3, 4} 이면 나올 수 있는 함수는 다음과 같다.

• solve(0) = 0 / solve(1) = 1 / ... / solve(10) = 3

여기서 우리는 앞에 나온 작은 함수값을 이용하여 큰 함수값을 재귀적으로 구할 수 있다는 점이다. 이를 수식으로 표현하게 되면

• sovle(x) = min(solve(x-1)+1, solve(x-3)+1, solve(x-4)+1)

이 재귀 함수의 기저 조건은 solve(0) = 0 이다. 왜냐하면 합을 0으로 만들기 위해서는 동전이 필요하지 않기 때문이다. 이를 일반적인 형태의 점화식으로 다음과 같이 나타낼 수 있다.

• solve(10) = sovle(7) + 1 = solve(4) + 2 = solve(0) + 3 = 3
• solve(x) = { 무한대 (x < 0), 0 (x = 0), mins solve(x-c) + 1 (x > 0) }

int solve(int x) {
	if (x < 0) return INF;
    if (x == 0) return 0;
    int best = INF;
    for (auto c: coins) {
    	best = min(best, solve(x-c)+1);
    }
    return best;
}

메모이제이션 (memoization)

동적계획법에서 메모이제이션은 중요한 요소이다. 이는 함수의 값을 계산한 뒤 이를 배열에 저장하는 방법을 말한다. 그러면 값이 다시 필요할 때마다 함수를 호출하지 않고도 값을 가져올 수 있게 된다. 이를 위 예시에다가 적용을 해보자.

• bool ready[N] : solve의 값이 계산되었는지
• int value[N] : 계산되었을 경우의 값을 저장

int solve(int x) {
	if (x < 0) return INF;;
    if (x == 0) return 0;
    if (ready[x]) return value[x];
    int best = INF;
    for (auto c : coins) {
    	best = min(best, solve(x-c)+1);
    }
    ready[x] = true;
    value[x] = best;
    return best;
}

반복문을 이용할 경우

value[0] = 0;
for (int x = 1; x <= n; x++) {
	value[x] = INF;
    for (auto c: coins) {
    	if (x-c >= 0) {
        	value[x] = min(value[x], value[x-c] + 1);
        }
    }
}