c++/알고리즘

[c++ DP] 다이나믹 프로그래밍 - 예제

hojung 2022. 5. 11.

728x90

1. Dynamic Programming이란?

동적계획법이라고도 하며, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고 다시 그 결과를 이용하여 큰 문제를 해결 할 때 사용하는 방식으로 프로그래밍 기법 중 하나이다.

그렇다면 위의 설명대로 결과를 저장할 공간이 있어야한다. 이렇게 되면 공간 복잡도 적인 측면에서 손해를 봐야하는데 왜 이러한 방법을 이용하는 것일까? 답은 간단하다. 조금의 공간 복잡도를 포기하더라도 시간 복잡도적인 측면에서 큰 이득을 볼 수 있기 때문이다.

알고리즘 문제를 풀다보면 엄청나게 큰 시간복잡도를 요구하는 문제들이 존재한다. 예를 들면 O(n!)이나 O(n^n)같은 알고리즘이다.(즉, 완전탐색과 같은 경우이다.) 하지만 Dynamic Programming즉 동적 계획법을 적용하여 문제를 풀면 위와 같이 시간복잡도가 어마어마하게 큰 문제들을 O(N^2)과 같은 형태로 줄일 수 있다.

위에서 동적 계획법은 작은 문제로 나누어 그 결과를 다시 큰 문제를 해결하는데에 사용하는 것이라고 언급했다. 이것은 조금 익숙한 개념일 수 있는데 우리가 중학교 수학 시간에 배웠던 점화식이 이와 유사한 형태이다. 하나의 case의 경우를 보고 규칙을 찾아내고 그 규칙을 전체에 대해 일반화 시키는 것 즉, 동적 계획법은 이러한 점화식을 찾아내는 것이 중요하다.

2. DP 예제-1

위와 같은 경우 문제를 완전탐색 방법으로 해결하려고 하면 어떻게 될까?

각 칸마다 이동할 수 있는 경우의 수는 3이므로 대략 O(3^n)정도가 될 것이다.... 인풋이 조금만 커도 이러한 형태의 알고리즘에서는 컴퓨터가 감당하지 못한다.

하지만 동적 계획법을 사용해서 점화식을 통해 문제를 해결하면 어떻게 될까?

우선 위의 문제에서 내려오는 방향이라고 하였다. 반대로 생각하면 한 칸이 존재할 때 위의 세 칸 (오른쪽 위 , 바로 위, 왼쪽 위) 중 가장 큰 값이 현재의 자신과 더해진다고 생각할 수 있을 것이다. 그렇게 되면 점화식은 다음과 같다.

map[i][j] += max( map[i-1][j-1], map[i-1][j], map[i-1][j+1])

이러한 방식으로 누적합을 구해가면 되는 것이다. 작성된 코드를 살펴보자

#define col 9
#define row 8
int colmax;
int maxi, maxj;
void numberGame(int twoDimension[][col]) {
    for (int i = 1; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (j == 0) {
                twoDimension[i][j] += (twoDimension[i - 1][j] < twoDimension[i - 1][j + 1] ? 
                    twoDimension[i - 1][j + 1] : twoDimension[i - 1][j]);//행의 왼쪽 끝일 때 [i-1][j] == 바로 위 < [i-1][j+1] == 오른쪽 대각선 위라면 더 큰 걸 더해준다. 두 가지만 고려한다. 
            }
            else if (j == col -1) {
                twoDimension[i][j] += (twoDimension[i - 1][j - 1] < twoDimension[i - 1][j] ? 
                    twoDimension[i - 1][j] : twoDimension[i - 1][j - 1]); //행이 오른쪽 끝일 때[i-1][j-1] = 왼쪽 대각선 위  < [i-1][j]바로 위라면 더 큰 걸 더해준다. 두 가지만 고려한다. 
            }
            else {
                //행의 중간이라면 왼쪽 대각선 위와 바로 위를 비교 바로 위와 오른쪽 대각선 위를 비교 왼쪽 대각선 위가 더 크다면 왼쪽 대각선과 오른쪽 대각선을 비교  제일 큰 값 더해준다. 
                twoDimension[i][j] += (twoDimension[i - 1][j - 1] < twoDimension[i - 1][j] ? 
                    twoDimension[i - 1][j] < twoDimension[i - 1][j + 1] ? twoDimension[i - 1][j + 1] : twoDimension[i - 1][j] : 
                    twoDimension[i - 1][j - 1] < twoDimension[i - 1][j + 1] ? twoDimension[i - 1][j + 1] : twoDimension[i - 1][j - 1]);
            }
        }
        if (i == row - 1) {
            cout << "-----------------------------------------\n";
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 9; j++) {
                    cout << twoDimension[i][j] << " ";
                }
                cout << "\n";
            }
            for (int i = 1; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (colmax < twoDimension[i][j]) {
                        colmax = twoDimension[i][j];
                        maxi = i;
                        maxj = j;
                    }
                }
                cout << "============================colmax=============================" << "\n";
                cout << colmax << " " << "maxi: " << maxi << "maxj: " << maxj << "\n";
                colmax = -10000;
            }
        }
        else continue;
    }
    int maxNum = 0;
    for (int i = 0; i < col; i++) {
        if (maxNum < twoDimension[row - 1][i]) maxNum = twoDimension[row - 1][i];
    }
    cout << maxNum << endl;
}

위의 코드에서 각 칸을 돌면서 각 칸에 대해 위의 세 칸의 값을 비교한 뒤 가장 큰 값을 자신과 더해주는 연산을 수행하고있다. 이렇게 누적합을 구해주면서 진행하면 어떤 방향으로 누적에 도달했는 지 또한 알 수 있다.

위의 코드에서는 점화식의 예외로 두가지 케이스를 들었는데 하나는 칸이 맨 왼쪽에 있는 경우 위에 존재할 수 있는 칸이 바로 위, 오른쪽 위 두 가지만 존재할 수 있는 경우이다. 다른 하나는 칸이 맨 오른쪽에 있어 위에 존재할 수 있는 칸이 바로 위, 왼쪽 위 두 가지만 존재할 수 있는 경우이다. 위의 코드를 수행하면 다음과 같이 나온다.

int main() {
    int twoDimension[row][col] =
    {
        {3,4,9,-2,2,51,-23,2,-1},
        {223,7,8,-11,5,-99,2,3,-4},
        {2,51,-23,-23,6,3,2,4,5},
        {5,-99,2,-1,32,2,5,-99,2},
        {6,3,3,-4,2,-1,6,3,3},
        {32,2,4,5,3,-4,2,-1,4},
        {4,4,23,6,2,-1,3,-4,34},
        {78,32,1,7,3,-4,-23,-23,6},
    };

    numberGame(twoDimension);

    return 0;
}

main함수

위와 같이 맵이 누적합의 결과로 나오는 것을 알 수 있었다. 마지막 열에서 가장 큰 수 403이 정답이 된다.

3. DP예제-2

단 쥐덫은 피해가야한다.

이 문제의 경우 위와 비슷하지만 제약 조건이 존재한다. 바로 쥐덫은 피해가야한다는 것이다. 이 같은 경우 동적 계획법에서 수행했듯이 점화식을 일반적으로 적용시키되 특정 조건이 있는 부분에서는 conitnue문을 이용해서 건너 뛰어 주면 된다. 밑의 코드처럼 말이다.

#include <iostream>
using namespace std;
#define Low  9
#define Col  9
int Solution(int map[][Col]) {
	map[0][0] = 0; // 시작 점 
	//map[i-1][j] == 바로아래 map[i][j-1] == 왼쪽
	for (int i = 0; i < Low; i++) {
		for (int j = 0; j < Col; j++) {
			if (map[i][j] == -1) continue;//덫이 있으면 건너 뛴다.
			if (i == 0 && j == 0) continue;// 처음 건너뛴다.
			if (i >= 1 && j >= 1) {
			 map[i][j - 1] >= map[i - 1][j] ? map[i][j] += map[i][j - 1] : map[i][j] += map[i - 1][j];
			}
			if(i == 0){
				map[i][j] += map[i][j - 1];
			}
			if(j==0) {
				map[i][j] += map[i - 1][j];
			}
		}
	}
	return map[Low - 1][Col - 1];
}

이 문제의 Recursive Property는 map[i][j] += max(map[i-1][j], max[i][j-1])과 같다.

단 위의 문제와 동일하게 i == 0 인 열과 j == 0인 경우를 따로 분리해서 생각해주었다.

결과는 5가나온다.

4. 결론

Dynamic Programming은 알고리즘의 스킬이라기 보다는 생각하는 방식이다. 알고리즘 문제를 접했을 때 완전탐색 문제이고 생각보다 훨씬 더 큰 시간 복잡도를 요구하는 문제라면 이DP를 생각해서 풀 수 있어야하겠다.

DynamicProgramming이란 완전탐색 + 기록 (memoization)과 같다. 많은 문제를 풀어보면서 더 문제를 볼 수 있는 눈을 키우는 것이 중요하다.