[동적 프로그래밍] DP의 유형과 예시 문제를 풀어보자.

이전에 코테를 공부할 때, DP 문제를 들여다봤다가 문제 제출 빈도도 낮고 평균점수도 낮다길래 풀어보질 않았다. 그 때 당시엔 시간낭비일거라 생각했다.(....) 그리고 대기업 코테를 보고나서, DP유형문제를 최대한 많이 풀어야겠다고 다짐하게 됐다.

매일매일 코테 한문제씩 풀던 것도 이제 깃에 풀이주석과 함께 커밋하려고 한다. 블로그에도 코테문제 해설을 적어보려하는데, 동적 프로그래밍이 그 시작이 되겠다.

-----------------------------------------------------------------------------------------------------------------------------------

 

동적 프로그래밍이 그리디와 다른 점은 그리디는 당장 눈 앞의 이익을 찾아내는 반면 동적 프로그래밍은 앞의 선택이 이후 선택에 영향을 주는 경우 사용된다. 그리디는 이전의 선택을 다시 고려하지 않는다는 것이다.

 

동적 프로그래밍이 이전 선택을 되돌아봐야하기 때문에 시간복잡도가 높게 나오지 않을까? 생각했지만 이를 위해 '메모이제이션' 개념이 있었다. 이전에 확인해보았던 선택은 다시 계산하지 않아도 되도록 기록을 해주는 것이다.

 

예를 들어보자. 대표적으로 피보나치 수열이 있다. 이전에 두 수를 더한 수가 현재의 수가 되는 수열이다.

1, 1, 2, 3, 5 이런 결과가 나왔다고 했을 때, 이러한 계산을 거쳤을 것이다.

f[0] + f[1] = 2

f[1] + f[2] = 3   <<< 이렇게.

그러면 f[1]을 반복적으로 계산하게 되는데, 메모이제이션을 쓰면 그럴 필요가 없다!

int memo[100];  // 메모이제이션 전역변수. 


int fibonacci(int num)
{
       if(num <= 1)
            return num;
       if(!memo[num])                   // 메모이제이션에 저장된 수가 0이 아닐때 (이미 계산된 수일 때)                        
            return memo[num];

       memo[num] = fibonacci(num - 1), fibonacci(num - 2);   // 계산 결과를 메모리제이션에 저장한다.
       return memo[num];
}

 

위와 같이 더 많은 메모리를 사용하는 반면 적은 시간복잡도를 가지는 코드를 만들 수 있다.

 

-----------------------------------------------------------------------------------------------------------------------------------

이제 예시 문제를 풀어보자.

 

문제 : 게임에서 산을 올라가는 길에 비석이 있다. 그 비석 마다 점수가 있으며 그 비석을 먹어 최대한 많은 점수를 얻어야 한다. 이 때, 세 개 연속으로 비석을 먹지 못한다. 그리고 마지막 비석은 무조건 먹어야한다.

 

입력 : 첫번째 줄 : 입력될 비석의 갯수

        두번째 줄 : 비석들의 점수

 

해설 : 마지막 비석은 먹어야한다는 힌트가 있다! 이를 이용해 식을 거꾸로 세워볼 수 있겠다. 

네번째 비석부터 선택지가 두 가지 있다. 

1. 바로 전 비석과 세번째 전 비석을 먹은 경우.  ●○●●

2. 두번째 전 비석을 먹은 경우.                      ○●○●

그렇다면 식은 memo[num] = max(memo[num - 3] + biseok[num] + biseok[num - 1], memo[num - 2] + biseok[num]) 이 되겠다. memo의 인덱스는 비석의 인덱스와 같고, 그 비석에서의 최선의 선택이 값으로 저장된다. 그러므로 다시 해당 인덱스의 최선의 선택을 알고자 할 때 memo배열을 이용하면 된다. 메모이제이션으로 계산 시간을 대폭 줄인 동적 프로그래밍 유형으로 풀 수 있다.

 

코드는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;
// 메모이제이션을 위한 전역변수
int memo[1000];

int solution(vector<int> biseok)
{
	memo[0] = biseok[0]; // 첫번째 비석은 자기자신만 먹는 선택지만 가진다.
	memo[1] = biseok[0] + biseok[1]; // 두번째 비석은 두가지 선택지를 가지지만 첫번째 비석까지 먹는 선택지가 항상 최선이다.
	memo[2] = max(biseok[1] + biseok[2], biseok[0] + biseok[2]); // 세번째 비석은 바로전 비석을 먹거나, 두번째 전 비석을 먹는 두가지 선택지가 있다.
	for (int i = 3; i < biseok.size(); ++i) // 네번째 비석부터 공통된 선택지 식을 가진다.
	{
		int first = memo[i - 3] + biseok[i] + biseok[i - 1]; // 세번째 전의 비석을 먹고, 바로 전의 비석을 먹는 경우
		int second = memo[i - 2] + biseok[i];				 // 두번째 전의 비석을 먹는 경우
		memo[i] = max(first, second);
	}

	return memo[biseok.size() - 1];
}
int main()
{
	int num;
	cin >> num;
	vector<int> biseok;

	for (int i = 0; i < num; ++i)
	{
		int temp;
		cin >> temp;
		biseok.push_back(temp);
	}

	cout << solution(biseok);
}