[Data Structure / Algorithms] DP(Dynamic Programming) (1)

전성훈·2023년 11월 2일

Algorithms datastructure swift

Data Structure-Algorithm

목록 보기

8/35

주제: Dynamic Programming을 제대로 푸는 방법

DP란

동적 프로그래밍(DP: Dynamic Programming)은 특정 유형의 문제를 다항 시간 내에 해결하는 방법입니다.

현실 세계에서는 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 있다. 이들은 컴퓨터로도 해결하기 어려운 문제이다.
그래서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.
어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있는데, 이를 다이나믹 프로그래밍(Dynamic Programming)기법으로 동적 계획법이라고 표현하기도 한다.
DP로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다.
이를 점화식으로 설명할 수 있다.

점화식이란) 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식
$a_{n+2} = f(a_{n+1}, a_{n}) = a_{n+1} + a_{n}$
이를 코드로 표현하면

func fibo(_ x: Int) -> Int { 
	if x == 1 || x == 2 { 
		return 1
	}
	return fibo(x - 1) + fibo(x - 2)
}

그런데 피보나치 수열의 소스코드를 이렇게 작성하면 심각한 문제가 발생한다.
바로 f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다.
예를 들어 n = 30 이면, 약 10억 가량의 연산을 수행해야 한다.
이 계산을 풀어서 확인해보면 동일한 함수가 반복적으로 호출되는 것을 알 수 있는데, 이를 활용하여 문제를 해결하면 재귀 함수를 활요한 문제보다 쉽게 해결할 수 있다.
이는 메모이제이션(Memoization)기법을 사용해서 해결하는 방법인데, 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.
즉, 메모이제이션은 값을 저장하는 방법이므로 캐싱이라도 한다.

// 개선된 피보나치 수열 계산 함수
// Memoization하기 위한 배열 생성 및 초기화
var dp = [Int](repeating: 0, count: 100)

func fibo(_ x: Int) -> Int { 
	if x == 1 || x == 2 { 
		return 1
	}
	
	// 이미 계산한 적 있는 문제라면 그대로 반환 
	if dp[x] != 0 { 
		return dp[x]
	}
	
	// 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
	dp[x] = fibo(x - 1) + fobo(x - 2)
	
	return dp[x]
}

DP문제를 푸는 방법

동적 계획법으로 풀기위해서는 두 가지 조건을 확인해야 한다.

큰 문제를 작은 문제로 나눌 수 있다.

작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

중복 부분 문제(Overlapping Subproblem)
- 실제 문제를 해결하기 위해 동일한 부분 문제의 해결책이 반복적으로 필요한 경우
- 이러한 문제는 중복 부분 문제 특성을 가진다고 말할 수 있다.
최적 부분 구조 특성(Optimal Substructure Property)
- 주어진 문제의 최적 해결책을 그 문제의 부분 문제들의 최적 해결책을 사용하여 얻을 수 있다면, 그 문제는 최적 부분 구조 특성을 가진다고 말할 수 있다.

DP 문제를 풀기위한 단계

문제가 DP 문제인지 확인한다.
- 문제를 해결하는 데 동일한 하위 문제가 반복적인 경우, 그리고 작은 하위 문제의 해결책을 결합하여 큰 문제의 최적해를 찾을 수 있는 경우 동적 프로그래밍으로 문제를 해결할 수 있다.
최소 parameters로 나타낼 수 있는 상태 표현(State Expression)을 결정한다.
- 상태 표현은 문제의 현재 상태를 나타내는 매개 변수 집합이다. 문제가 해결되는 데 필요한 정보를 포함하고 있어야 한다. 하지만 최소한의 매개 변수를 사용하여 문제를 해결할 수 있어야 한다.
그 식을 가공하고 식 간의 관계를 찾는다. (점화식으로 만든다.)
- 상태와 전의 관계를 사용하여 작은 하위 문제의 해결책을 결합하여 큰 문제의 최적해를 찾을 수 있다. 이 단계에서, 각 상태에서 가능한 모든 전이 관계를 식별하고, 각 전이 관계가 현재 상태와 적절한 하위 문제 상태 간의 관계를 유지하는지 확인한다.
tabulation 또는 memorization을 실시한다.
- Tabulation(Bottom-up) 또는 Memorization(Top-down)을 사용하여 문제를 해결한다.

1단계, 어떻게 문제를 DP 문제로 분류할까

일반적으로, 특정 양을 최대화 또는 최소화해야 하는 문제 또는 특정 조건 또는 특정 확률 문제에서 배열을 계산해야 하는 문제를 동적 계획법으로 해결할 수 있다.
모든 동적 계획법 문제는 중복된 하위 문제 속성을 만족하며, 대부분의 고전적인 DP 문제 또한 최적 부분 구조를 만족시킨다. 일단 주어진 문제에서 이러한 특징들이 확인되면, DP를 적용하여 해결할 수 있다.

2단계, 상태 결정하기

DP 문제는 모두 상태와 전환에 관한 것들이다. 두 번째 단계는 상태 전환이 선택한 상태 정의에 따라 달라지기 때문에 매우 신중하게 수행되어야 하는 가장 기본적인 단계이다.
상태는 특정 위치를 고유하게 식별하거나 주어진 문제에 서있는 매개 변수 집합으로 정의할 수 있다.

3단계, 상태 간의 관계 형성 (점화식 세우기)

예시 문제

3개의 숫자 {1, 3, 5}가 주어지고, 주어진 세 숫자의 합을 사용하여 숫자 'N'을 형성할 수 있는 총 방법 수를 구하라.

ex) 6을 형성하는 총 방법 수: 8
1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 3
1 + 1 + 3 + 1
1 + 3 + 1 + 1
3 + 1 + 1 + 1
3 + 3
1 + 5
5 + 1
문제를 해결하기 위해선 직관을 기르는 연습이 필요하다.
주어진 숫자를 형성하기 위해 1,3 또는 5만 사용할 수 있다. n = 1,2,3,4,5,6에 대한 결과를 안다고 가정했을 때, 우리는 상태 (n = 1), (n = 2), (n = 3)...... (n = 6), (n = 7)의 결과를 전의 결과의 경우의 수를 더함으로 써 알 수 있다. 예를 들면
n = 7 일 때 모든 경우의 수를 구하려고 한다면,
예) n = 6 일 때: 가능한 모든 상태 조합에 1 더하기
- [(1 + 1 + 1 + 1 + 1 + 1) + 1]
- [(1 + 1 + 1 + 3) + 1]
- [(1 + 1 + 3 + 1) + 1]
- [(1 + 3 + 1 + 1) + 1]
- [(3 + 1 + 1 + 1) + 1]
- [(3 + 3) + 1]
- [(1 + 5) + 1]
- [(5 + 1) + 1]
예) n = 4 일 때: 가능한 모든 상태 조합에 3을 더하기
- [(1 + 1 + 1 + 1) + 3]
- [(1 + 3) + 3]
- [(3 + 1) + 3]
예) n = 2 일 때: 가능한 모든 상태 조합에 5를 더하기
- [(1 + 1) + 5]
위의 식을 보면 state (7) = state(6) + state(5) + state(4) 이다. 즉,
state(n) = state(n-1) + state(n-2) + state(n-3)가 된다.
코드로 나타내면

func solve(_ n: Int) -> Int {
    if n < 0 {
        return 0
    }
    if n == 0  {
        return 1
    }
    return solve(n - 1) + solve(n - 3) + solve(n - 5)
}

위의 코드는 동일한 상태를 재귀적으로 반복해서 계산하므로 연산 시간이 기하급수적으로 늘어난다.
Time Complexity: O(3^n)을 나타낸다.

4단계, 상태에 대한 Memoization 또는 Tabulation 생성

Top-down 형식인 Meomoization 방식을 활용하면 재귀적 함수를 사용했던 시간 복잡도 대신 O(n)의 시간 복잡도를 나타내면서 문제를 풀 수 있다.

var dp = [Int](repeating: 0, count: 100)
func solve(_ n: Int) -> Int { 
	if n < 0 { 
		return 0
	}
	if n == 0 { 
		return 1 
	}
	if dp[n] != 0 { 
		return dp[n]
	} else { 
	 dp[n] = solve(n - 1) + solve(n - 3) + solve(n - 5)
	}
	
	return dp[n]
}