YepBt
1k
2020-04-30 11:34:28
3
1886

알고리즘, 이해하고 사용하자, 다이나믹 프로그래밍, 동적 계획법


저번에는 우리는 알고리즘을 어떻게 공부하면 좋을지에 대해서 알아보았습니다.


자, 이제 공부하는 법을 알았으면 공부를 해야합니다. 간단하게나마 알고리즘 문제를 풀 때 어떤 사고를 하면서 문제를 풀어야 하는지를 최대한 서술을 해보고자 합니다.

사실 밑천이 드러날 때가 되어서 알고리즘 관련해서는 안적으려고 했는데, 많은 분들이 공감을 해주셔서, 조금이나마 도움을 드려보고자 글을 더 써봅니다.


여러 알고리즘이 있지만 우선 동적 프로그래밍에 대해서 알아보려고 합니다.


제가 쓴 글들을 읽어보신 분들은 이제 느낄 수 있겠지만, 저는 세상에 어떤 일이든 생각하면 원인과 결과, 혹은 이유를 분석 할 수 있다고 하는 주의입니다.

그래서 가장 중요하는 것은 논리적으로 생각하려고 하는 것입니다.


알고리즘도 마찬가지입니다. 내가 해당 알고리즘을 이해를 하고 있어야 문제를 풀 수 있습니다.



## 다이나믹 프로그래밍, 동적 계획법이란?

다이나믹 프로그래밍이 과연 무엇일까요? 메모이제이션, 분할정복 등 단어들을 들어보셨을 것입니다.


다이나믹 프로그래밍이란 큰 문제를 작은 문제로 나누어 푸는 알고리즘입니다.

하지만 이렇게 보면 비슷한 알고리즘이 있습니다. 분할정복이란 알고리즘이죠. 이름명에서도 분할을 하여 정복한다. 큰 문제를 작은 문제로 나누어 푸는 알고리즘이라는 뜻입니다.

과연 그러면 다이나믹 프로그래밍과 분할정복은 어떤 점이 다를까요? 핵심은 다이나믹 프로그래밍의 경우 작은 문제의 "답이 변하지 않는다"라는 점입니다.


그래서 내가 작은 문제의 답을 알고 있으면 더 큰 문제도 보다 빨리 해결 할 수가 있습니다.


**"최대한 설명을 자세히 하기 위해서 지루 할 수 있습니다."**



가장 유명한 예시가 바로 피보나치 이죠. 피보나치로 알아보도록 하겠습니다. 0 1 1 2 3 5 8 13 21 ...

이 예시를 이제 개발자가 생각하기 쉽게


fibonacci[0]=0, fibonacci[1]=1, fibonacci[2]=1, fibonacci[3]=2, fibonacci[4]=3, fibonacci[5]=5, fibonacci[6]=8


라고 생각을 해봅니다.


피보나치의 규칙성이 무엇인가요? fibonacci[현재의 값] = fibonacci[현재의 값 - 1] + fibonacci[현재의 값 - 2] 이라는 것을 알 수 있습니다.


예시 문제로 7번째 피보나치에는 어떤 값이 올까요?

이 과정을 위해 7번째 피보나치를 구하기 위해서는 6번째 피보나치 값과 5번째 피보나치 값을 구해서 더해야 합니다. 앞으로 표기를 위해 fibonacci[6], fibonacci[5]라고 하겠습니다.

조금 설명을 드리자면 fibonacci[6] = 6번째 피보나치 값입니다.


그러면 fibonacci[7] = fibonacci[6] + fibonacci[5]이고, fibonacci[6]을 모르면 어떻게해야할까요? 당연히 구해야합니다. fibonacci[6]을 구하기 위해서 fibonacci[4]+fibonacci[5]를 해야합니다.


fibonacci[7] = fibonacci[4] + fibonacci[5] + fibonacci[5]가 되었네요. 이제 fibonacci[5]의 값을 모르면 어떻게 할까요? 당연히 구해야 합니다. fibonacci[5]를 구하기 위해서는 fibonacci[4] + fibonacci[3]을 해야하네요.


fibonacci[7] = fibonacci[4] + fibonacci[4] + fibonacci[3] + fibonacci[4] + fibonacci[3]가 되었습니다.


그리고 fibonacci[4]를 알기 위해선 fibonacci[2] + fibonacci[3]이니 fibonacci[2]도 알아야 하구요. 더 스텝을 밟기엔 복잡해지니 생략하겠습니다.


이정도 왔으면 이제 느낀 점이 있을 것입니다. fibonacci[7] = fibonacci[4] + fibonacci[4] + fibonacci[3] + fibonacci[4] + fibonacci[3]에서 

내가 fibonacci[4]의 값과 fibonacci[3]의 값, 단어로 변환하면 4번 째 피보나치의 값과 3번 째 피보나치의 값을 알고 있다면,


아니면 그 이전에  fobinacci[7] = fibonacci[4] + fibonacci[5] + fibonacci[5]에서 5번 째 피보나치 값과 4번 째 피보나치 값만 알고 있다면,


혹은 더 그 이전에 fibonacci[7] = fibonacci[6] + fibonacci[5]에서 6번 째 피보나치 값과 5번 째 피보나치 값만 알고 있다면 더 편하게 7번 째 피보나치 값을 구할 수 있겠구나.


종합해보자면, 5번째 6번째의 피보나치 값만 안다면 굳이 3번째, 4번째, 피보나치 값, 더 나아가 첫 번째 피보나치 값이 무엇인지를 일일히 구할 일이 없습니다.

작은 케이스에 대한 답을 저장한다. 이것이 바로 메모이제이션입니다. 그리고 작은 케이스에 대한 값(fibonacci[5], 5번 째 피보나치 값)은 변하지 않는다. 방식이 바로 다이나믹 프로그래밍의 특성입니다.


그리고 작은 케이스에 대한 저장을 하지 않는다면, 아래 수식에서 4번째 피보나치 값을 3번이나 새로 구해야, 3번째 피보나치 값을 2번이나 다시 구해야합니다.

fibonacci[7] = fibonacci[4] + fibonacci[4] + fibonacci[3] + fibonacci[4] + fibonacci[3]


만약 1000번째 피보나치 값을 구한다면? 당연히 더 많은 4번째 피보나치 값을 최소 수백번에서 수천번은 구하게 생겼습니다.

작은 케이스에 대한 답을 저장해둠으로 같은 케이스에 대해서는 값을 새로 구할 필요가 없다 라는 느낌만 가져가시면 좋을 것 같습니다.


## 예제 통해서 다이나믹 프로그래밍 알아보기

다이나믹 프로그래밍에서 가장 중요한 점은 "작은 케이스에 대해 답을 저장해야하는 필요성 + 그리고 현재의 값을 구하기 위한 규칙성 찾기"입니다.

피보나치의 경우에는 1차원이었지만, 좀 더 복잡한 상황을 고려한다면 2차원의 배열까지는 사용해서 상황들을 정리해야 할 수 있습니다.


이번에는 실제로 예제를 보도록 하겠습니다. 아래 문제를 한 번 읽고 오시길 바랍니다.


https://www.acmicpc.net/problem/2579


문제는 별다른 설명이 필요없습니다. 계단 오르며 점수를 얻는 그런 게임이라니까요. 문제는 규칙이죠


1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.


피보나치의 경우 그냥 현재 값보다 이전 단계의 답(현재의 값 -1), 그 이전 단계의 답(현재의 값 - 2)만 알면 되었습니다.


하지만 이 문제는 조금 복잡하게 느껴집니다. 연속으로 계단을 세번 올라오면 안된다네요. 최대 2번까지만 연속으로 밟을 수 있는 것입니다.


규칙성을 한번에 찾으려고 하면 생각이 정리가 안되어 힘들 수 있습니다. 예시를 생각해봅시다.


5번째 계단에서 최고 점수를 받는 경우는 어떤게 있을까요?


5번째 계단에서 최고 점수를 받는 경우는 아래 케이스가 있습니다.


당연히 5번째 계단에서 최고점수를 받으려면 5번째 계단을 밟으면 무조건 이득입니다. 문제 조건에서 마이너스 점수 등이 없기 때문이죠. 그래서


1. 3번째 계단을 안 밟고, 4번째 계단을 밟고, 5번째 계단을 밟는 경우

2. 4번째 계단을 안 밟고, 5번째 계단을 밟은 경우(3번째 계단을 밟거나, 안 밟은 경우)


로 2가지 입니다.


1번의 경우 연속으로 3번째 계단을 안 밟고, 4번째 계단을 안 밟을 수 있습니다. 문제에는 해당 부분에 관련된 제약이 없기 때문이죠. 그래서 


그러면 위의 상황에서 어떤게 최대값 일까요? 3번 째 계단이 100점이고, 4번째 계단이 10점인 경우 1번이 답일 수 있습니다. 하지만 3번 째 계단이 10점이고, 4번째 계단이 100점인 경우, 2번이 답일 수 있습니다. 그래서 우리는 두 경우를 모두 고려해야합니다.

이 부분에서 가장 골치 아픈 부분은 n번째 계단을 밟았을 때 그 이전에 계단을 밟았는지 안 밟았는지에 대한 상태까지 알고 있어야 한다는 점입니다.


저의 경우에 상태를 체크하기 위해 이중 배열을 사용하여 계단[n번째 계단][경우의수]라고 가정하여 사용하였습니다.

경우의 수는 딱 두가지 케이스가 옵니다. 


[경우의수]

1. n번째 계단이 연속으로 2번째인 경우

2. 이전에 점프를 해서 n번째 계단이 첫 번째 계단인지를 의미합니다.


위의 케이스와 함께 생각하면 됩니다.


1. 3번째 계단을 안 밟고, 4번째 계단을 밟고, 5번째 계단을 밟는 경우(위 경우의 수 중 1번에 해당합니다.)

2. 4번째 계단을 안 밟고, 5번째 계단을 밟은 경우(위 경우의 수 중 2번에 해당합니다.)


그러면 이제 이 경우의 수에 따라 수식으로 표현을 해야합니다. 그래야 코딩하기 쉬우니까요.


계단[n번째][n번째 계단이 연속으로 2번째인 경우]의 점수들의 합 = 계단[n번째]의 점수 + 계단[n번째-1][이전에 점프를 해서 첫 번째 계단인 경우]의 점수들의 합

계단[n번째][이전에 점프를 해서 첫 번째 계단인 경우]의 점수들의 합 = 계단[n번째]의 점수 + max(계단[n-2번째][이전에 점프를 해서 첫 번째 계단인 경우]의 점수들의 합, 계단[n-2번째][n번째 계단이 연속으로 2번째인 경우]의 점수들의 합)


이 되겠습니다. 위의 수식처럼 보면 너저분해 보일 수 있습니다. 간단한 수식으로 바로 보여드리거나 하면 알고리즘을 처음 공부하는 분들께는 힘들 수 있습니다. 그래서 최대한 세세하게 설명을 드리고자 한 것이니. 양해 부탁드립니다.


혹시 이런 생각을 하시는 부분이 있을 수 있습니다.


"그러면 6번째 계단에서, 5번째 계단은 안 밟고 이득인 경우가 나올 수 있는거 아니야?"


6번째 계단에서 최고 점인 경우는 위의 제가 설명드린 최고점을 구하는 케이스에서 

2. "5번째 계단을 안 밟고, 6번째 계단을 밟은 경우(4번째 계단을 밟거나, 안 밟은 경우)"에 해당합니다. 그리고 이에 대한 수식은


계단[n번째][이전에 점프를 해서 첫 번째 계단인 경우]의 점수들의 합 = 계단[n번째]의 점수 + max(계단[n-2번째][이전에 점프를 해서 첫 번째 계단인 경우]의 점수들의 합, 계단[n-2번째][n번째 계단이 연속으로 2번째인 경우]의 점수들의 합)

였습니다. 이거를 보시면 알겠지만 5번째 계단을 안 밟는 경우는 4번째 계단에서 최대값을 가지는 것이기 때문에, 고려를 할 필요가 없습니다.


이것을 기반으로 코딩을 하면 대략 아래와 같은 결과가 나옵니다.


int main()

{

int n;

int arr[300]; //각 계단의 점수를 저장할 변수

int dp[301][2] = {}; //각 계단에서의 최고 점수를 저장할 다이나믹 프로그래밍 변수

cin >> n;

int r;

for (int i = 0; i < n; i++)

{

scanf("%d", &arr[i]);

}

dp[0][0] = arr[0];

dp[0][1] = arr[0];

dp[1][0] = arr[1] + arr[0];

dp[1][1] = arr[1];

for (int i = 2; i < n; i++)

{

dp[i][0] = arr[i] + dp[i - 1][1];

dp[i][1] = arr[i] + max(dp[i - 2][0], dp[i - 2][1]);

}

cout << max(dp[n - 1][0], dp[n - 1][1]) << endl;

return 0;

}


다이나믹 프로그래밍을 설명드리고자 글을 한번 써보았는데, 너무 복잡해 보일 수도 있습니다.

알고리즘은 원래 생각하기 싸움입니다. 누군가한테는 이런 과정에 대한 설명이 필요하다고 생각되어, 당연한 것도 다시 한번 확인함으로 나쁠 것이 없기 때문에, 당연한 피보나치부터해서 다루어보고, 예제를 통해 최대한 내가 어떤식으로 생각을 해야하는가에 대해 초점을 맞춰서 설명을 해보았습니다.

감사합니다.


https://spellofstar.github.io/post/algorithm_dynamic_programming/

7
6
  • 댓글 3

  • 개발자만다린
    -18
    2020-05-06 00:35:36

    "n번째"라는 말은 이제 좀 바꿔야 겠습니다.

    "i번째"로? ㅎ

    0
  • 정보정보
    144
    2020-05-07 15:39:25

    글 하나하나 학습의 깊이가 대단하신것 같습니다


    감사합니다!

    0
  • 숭잼
    92
    2020-05-16 09:41:30

    좋은 글 감사드립니다

    0
  • 로그인을 하시면 댓글을 등록할 수 있습니다.