강의/computer science

[computer science] Dynamic Programming (동적 프로그래밍)

하기싫지만어떡해해야지 2024. 11. 20. 11:49

이 게시글은

서울대학교 데이터사이언스대학원

조요한 교수님의

데이터사이언스 응용을 위한 컴퓨팅 강의를

학습을 위해 재구성하였습니다.


Dynamic Programming에 대해

배운 내용을 정리해보도록 하겠다

 

 

학창시절을 보내다보면 한 번쯤은 들어봤을

피보나치 수열

 

피보나치 수열은 각각의 숫자가 앞의 두 숫자의 합으로

이루어져있는 수열로

피보나치 수열을 위와 같이 점화식으로 나타낼 수 있다

 

 

이는 대표적인 Divide and Conquer 방식인데

일반적으로 어떤 problem을 작은 subproblem으로 나누는것이다

 

위 ppt에서의 코드를 보면

피보나치 함수를 정의해놓고 있다

 

Fib함수 내에서 계속해서 Fib를 호출하면서

recursive하게 구현하였고

n이 0이거나 1일 때 0 또는 1의 값을 리턴한다

 

이렇게 구현한 피보나치 함수의 call stack을

트리로 표현하면 ppt의 오른쪽처럼 표현할 수 있다

 

저 tree를 자세히 보면 같은 subproblem을

여러 번 반복해서 푼다는 것을 알 수 있다

 

Fib(n-2)는 앞에서 풀었는데

뒤에서 반복해서 또 풀고있는 것을 볼 수 있다

 

이러한 방식의 time complexity는

O(2 n제곱)이다

왜냐하면 n이 1 또는 0이 될때까지

진행되기 때문이다

 

 

그렇다면 이 Fib 함수에서

이미 앞에 계산한 Fib 값이 뒤에서도

반복해서 나온다는 것을 알았으니

미리 계산한 Fib 값을 저장해주도록 하자

 

그래서 그 값을 저장한 F라는 list를 생성한다

이렇게 해주면 이전에 한 번 계산했던 값이라면

그냥 list에서 index를 찾아서 반환하게 된다

 

이렇게 하면 총 n번만 계산을 하면 되므로

time complexity는 O(n)이 걸리고

함수 실행 시 call stack을 트리로 나타내면

오른족과 같아진다

 

이렇게 이전에 계산한 값을 미리 저장해 놓고

이후 연산에서 사용하는 것을

dynamic programming에서 memoization이라고 하는데

dynamic programming에서 굉장히 중요한 개념이다

 

 

dynamic programming에서의 다른 예시를 살펴보자

위와 같이 총 n칸의 계단을

1칸 또는 2칸씩만 움직여서 모두 올라가려고한다

올라갈 수 있는 모든 방법의 개수는 몇 개일까?

 

 

이러한 문제를 풀 때 어떻게하면 효율적인 코드를 작성하는지

고민하는 것도 중요하지만

너무 효율적인 코드에 집착하기보단

그냥 하나하나 해본다면 어떻게 되는지 생각해보는 것도 중요하다고 한다

 

만약 나에게 무한의 시간과 무한의 공간이 주어진다면

이 문제를 어떻게 해결할 것인지

고민하는 과정에서 알고리즘 실력이 늘 수 있을 것 같다

 

우선 위 같은 경우는에서는

ways[i]를 총 i칸 올라가는 방법이라고 한다면

i보다 1번째 적은 칸에 도착해서 남은 1칸을 더 가는 것

i보다 2번째 적은 칸에 도착해서 남은 2칸을 더 가는 것

 

위 두개의 합이 총 i칸을 올라가는 방법의 개수가 될 것이다

 

따라서 이걸 점화식으로 나타내면

ways[i] = ways[i - 1] + ways[i -2]가 된다

 

그 다음에 base case를 정의를 해주는데

기본적으로 0층에 도달하는 방법은

그냥 안움직이는 방법 1개이므로 1가지 방법

1층에 도달하는 방법도 1가지 방법이므로

ways[0] = 1

ways[1] = 1

이렇게 정의를 해준다

 

이러한 방법의 time complexity는

O(n)이 된다

 

 

 

Dynamic Programming

 

Dynamic Programming이란 복잡한 문제를

해결해가는 테크닉이다

 

기본적인 아이디어는 큰 problem을

작은 subproblem으로 나누어서 해결하고,

subproblem들의 결과값이 다른 문제들을 푸는데 계속 사용되는 것이다

 

궁극적으로 구하고자 하는 optimal solution이

subproblem의 optimal problem으로 해결이 가능할 때

dynamic programming이 굉장히 유용해진다

 

여기서 programming이라는 단어는

우리가 아는 단순 코딩 programming은 아니고

tabular method를 말하는 것이다

 

 

그렇다면 divide and conquer 방식과의 차이점은 무엇일까?

 

merge sort는 대표적인 divide conquer 방식인데

array의 반을 잘라서 sort하고

다시 merge해서 sort하는 방식이다

 

divide conquer는 기본적으로 subproblem들이

각각 independent하다

 

subproblem들을 recursive하게 풀어서

combine하는 것은 같지만

subproblem들 간에 share하는 informaion이 없다

 

 

반면에 dynamic programming은

subproblem을 overlapping한다

 

이 말은 즉, subproblem의 solution을

나중에 다시 reuse한다는 것이다

이것이 가장 핵심적인 차이이다

 

 

Dynamic Programming에는 4가지 step이 있다

 

1. state define하기

subproblem을 어떻게 정의할 것인가

그리고 어떻게 나타낼 것인가를 정하는 단계이다

 

위의 예시에서 보자면

ways[i]는 i칸 올라가는 방법의 개수라고

정의를 내린 것이 이 단계이다

 

2. establish recursive relation

large problem을 small problem으로 정의하는 과정이다

problem을 어떻게 함수로 나타낼 수 있을지를 결정한다

ways[i] = ways[i-1] + ways[i-2]로 정의한 것이

이 과정에 해당한다

 

 

3. Define Base Case

base case를 정의하는 과정이다

함수가 Recursive하게 수행되다가 어느 순간 멈춰야하는데

그걸 정의해주는 것이 base case이다

 

따라서 simplest instance가 무엇인지 찾아서 정의해주고

그 친구들이 문제의 foundation이 된다

 

위 예시에서는 ways[0] = 1, ways[1] = 1이

base case가 된다

 

4. implement the solution iteratively or recursively

bottom-up(iteratively)으로 구현할건지

top-down(recursively)로 구현할건지와 같이

구체적인 구현을 수행하는 부분이다

이 부분에서는 memoization이 매우 중요한 역할을 한다

 

 

이제 Dynamic Programming의 다른 예시를 살펴보고

같이 풀어보자

 

길이가 n인 토막이 있고

길이 i에 따라 Pi는 얻을 수 있는

Revenue이다

 

길이 n인 토막을 어떻게 자르면

가장 많은 돈을 벌 수 있을까?

 

 

만약 총 길이 n이 4라고 해보자

 

그러면 총 8가지의 자리는 방법이 있다

 

아예 안자르면 길이가 4가 되므로 revenue는 9

1/3만큼 자르면 1 + 8 = 9

2/2만큼 자르면 5 + 5 = 10

...

이런식으로 진행되게 된다

 

따라서 위 경우를 모두 살펴보면

2/2가 10으로 가장 높은 수익을 준다는 것을 알 수 있다

 

우선 길이 n의 나무 토막을 자르는 방법은 몇 개가 있을지 생각해보자

 

기본적으로 n-1개를 자를 수 있는 가능성이 있고

각각의 position에서 자를 수도 있고 안 자를 수도 있다

 

그렇게 때문에 총 경우의 수는 2의 n-1제곱 개가 되고

정말 근본적으로 한다면 모든 경우의 수를 다 구해볼 수도 있을 것이다

 

하지만 dynamic programming을 이용해서

조금 더 효율적으로 해결방안을 찾아보고자한다

 

 

우선 state를 정의해보자

 

r(n)은 길이가 n일 때의 maximum revenue이다

 

rod를 젤 앞에서 한 토막을 내면 나머지는 n-1토막이 된다

그럼 p(1) + r(n-1)이 이 경우에 가장 최적의 수익이 될 것이다

 

앞에서 2토막을 내면

p(2) + r(n-2)가 가장 최적의 수익이 될 것이다

 

이러한 식으로 마지막에는 한 개도 자르지않는 경우인

p(n)이라는 식이 나오게 되고

 

이 총 n개의 식 중에서

결과값이 가장 큰 것이

r(n)이 되는 것이다

 

따라서 이 식의 점화식은

r(n) = max(처음 토막 길이만큼의 가격 + 남은 토막의 수익의 최댓값)

이 되는 것이다

 

 

naive한 algorithm의 pseudo code를 한 번 보자

cut-rod라는 함수를 만들고

각각의 토막별 가격을 담고있는 p와 토막의 길이인 n을 받아온다

 

n이 0인 경우는 그냥 0이고

i는 1부터 n까지 처음의 시작 길이를

처음 길이를 몇으로 자를건지를 나타낸다

 

따라서 q의 값은 위와 같은 식이 나오고

q를 리턴해주는 형태가 된다

 

이전에 나온 결과값을 저장하고 있지 않기 때문에

똑같은 것을 반복해서 계산하고 있어서

조금 느릴 수는 있지만 정확하게 풀 수 있다

 

subproblem들이 작동하는 원리를 tree로 나타낸 것이다

n이 4라고 가정해보자

각각의 노드는 cut-rod의 인자들이고

cut-rod 4가 호출이 되면 cut-rod 3이 호출이 되고

이렇게 recursive하게 호출이 된다

 

위 tree를 확인해보면

계속 똑같은 문제를 recursive하게 반복을 해서

호출을 하는 것을 확인할 수 있다

 

그런데 naive algorithm에서는 이전에 계산했던 것을

따로 저장해두지 않기 때문에 계속해서 계산을 하게된다

 

 

naive algorithm의 time complexity를 보자

T(n)이 cut-rod가 호출되는 횟수인데

recursive하게 돌면서 호출을 해서

T(n) = T(n-1) + T(n-2) + ... + T(0)이 된다

 

저 상태에서 T(n)에서 T(n-1)을 뺴주면

T(n)은 2의 n제곱이 되고

 

time complexity는 n의 exponential이 된다

 

memoization을 이용한 dynamic programming으로

top-down 방식으로 구현을 해보자

 

처음에 4가 호출된다면 그 다음에는 3이 호출된다

그리고 3이 호출되면 2->1->0 이 순서로 호출이 된다

 

그러면 3, 2, 1의 값은 이때 다 계산이 되어서

어딘가에 결과값이 저장이 되어있을 것이다

 

0까지 마친 뒤 다시 위로 올라가면

2번째 height에서 2로 가게 된다

 

그런데 2는 이미 사전에 계산을 해뒀으니

그 값을 가져온다

 

또한 원래대로라면 2->1->0으로 내려가야하지만

이미 밑의 값들 모두 계산이 되어있어서

계산을 해줄 필요가 없이 값만 가져오면 된다

따라서 굳이 내려가줄 필요가 없다

 

이런식으로 memoization을 활용하면

호출 횟수가 확 줄어들게 된다

 

 

top-down approach의 pesudo code이다

 

크게 2가지로 나눌 수 있다

 

첫 번째 코드는 단순하게 계산의 결과값을

저장할 공간을 만들어주는 코드이다

 

그런 다음 밑 부분에서 recursive하게

cut-rod 메소드를 수행하는데

r(n)이 0이상이라는 소리는 처음 초기화했던 - 무한대값에서

한 번 업데이트가 된 적이 있다는 뜻이고

이는 이미 계산된 결과가 있다는 것을 의미한다

 

따라서 그럼 저장된게 있다고 판단을 하는 것이고

코드 전체를 실행하지 않고 그냥 값을 가져와서 실행을 하게 된다

 

top-down approach는 오른쪽과 같은 식으로

그 관계를 그릴 수 있다

 

처음에는 아무 것도 저장된게 없어서 4 3 2 1을 가다가

끝나면 돌아온다

 

그 다음에 2로 가는데

이 부분은 이미 다 호출이 된 부분이기 때문에

바로 0으로 갔다가 다시 올라온다

 

이러한 과정을 반복해서 보면

결과적으로 각각의 subproblem은 각 1번씩만 풀리게 된다

따라서 이 방식에서는 총 time complexity는

n + (n-1) + ... + 1 = n2제곱이 되어서

O(n2제곱)이 된다

 

 

이제 bottom-up approach를 한 번 보자

 

아래에서부터 위로 채워나가는 방식이다

짧은 rod를 계산하고 그 다음 더 큰 rod를 계산한다

 

따라서 rod가 0, 1일 때를 먼저 계산한다

그럼 rod2는 0과 1에서 참조를 해서 쭉쭉 계산하고

그런 방식으로 문제를 해결해나가는 방식이다

 

보통은 bottom-up 방식이 top-down방식보다

implementation이 조금 쉽다

그리고 recursively 구현하는 top-down방식에 비해

overhead도 조금 편이다

 

왜냐하면 recursive하게 구현하게 되면 메모리 stack에서 계속

pop, push, pop, push가 반복되고

그렇게 되면 하드웨어에서 시간이 오래 걸릴 수가 있다

 

하지만 bottom-up은 그런 경향이 상대적으로 적다

 

bottom-up approach의 pseudo code이다

 

q를 계산해서 r[j]에 저장한다

여기서 중요한 것은 recursive call이 되지 않는다는 것이다

 

 

top-down과 bottom-up approach는 asymptotic하게는

동일한 running time을 갖고 있다

 

하지만 bottom-up은 recursion을 사용하지 않으면서

call stack을 절약할 수 있고

0부터 순차적으로 접근을 하기 때문에

메모리 locality로 인해 접근 속도도 빠르다

 

반면에 recursive는 어떻게 구현을 하냐에 따라서

메모리 여기 저기에서 가져올 수가 있어

상대적으로 접근효율이 떨어진다

 

그렇다고 해서 bottom-up이 항상 좋은건 아니고

case by case이다

 

지금까지는 max revenue를 구하는 문제만 풀었다

 

하지만 이제 궁금한건

max revenue에 도달하는 실제 cut의 configuration을

어떻게 구할 것인지 이다

 

따라서 s라는 것을 반환할건데

이 s는 길이가 j인 것을 잘라서 max revenue를 얻고 싶은데

앞에서 몇 번째 위치에 잘라야 max revenue가 되는지를

나타내는 값이다

 

 

구현은 위와 같이 한다고 한다

앞에서 봤던 코드와 비슷하지만 s가 추가되었다

 

max값이 되었을 때 i를 s에 함께 저장한다

그런 다음 r과 s를 함께 반환한다

 

이런식의 코드를 사용하면 solution을 reconstruct가 가능하다

 

i가 0이라고 하면 토막의 길이가 0일 때의 가격이다

i가 3일 때의 max revenue는

s가 3인걸 보아하니 그냥 3을 통째로 자른 값이

max revenue가 되는 것을 알 수 있다

 

중요한 것은 i = 4부터이다

max revenue가 s가 2일 때 발생했다

가장 첫 토막을 2개로 잘랐더니

max revenue인 10이 발생했다는 소리이다

 

길이가 5일 때도 살펴보자

s = 2인 것을 보니 앞에서 2칸을 잘랐을 때

길이가 max가 되었다는 뜻이다

따라서 max revenue는 13이다

 

i가 6인 경우는 그냥 6을 통째로 갖는 경우가

max revenue인 17이 되고

 

i가 7인 경우는 앞에서 1칸 잘랐을 때가 가장 수익이 커졌고

그래서 p(1)의 값인 1과

남은 길이인 16의 max revenue인 17이 더해져

총 max revenue가 18이 된 것을 볼 수 있다

 

 

간단하게 greedy algorithm에 대해 살펴보고

오늘의 수업내용 정리는 마무리를 해보려고한다

 

dynamic programming은 앞에 나왔던 subproblem에서 

optimal solution을 찾고 그걸 이용해서

미래에 일어날 일에 대해 informed choice를 만드는 것이었다

 

하지만 greedy algorithm은 그렇게 하지 않고

그냥 initial greedy choice를 만들고

남은 subproblem을 푸는 방식이다

 

중요한 가정은 locally optimal한 choice가

globally optimal한 solution으로 이어진다는 것이다

 

어떤 global한 optimal solution이 subproblem의 optimal solution으로

이어질 수 있을 때 이걸 greedy algorithm이라고 부른다

 

그냥 각각의 순간마다 best choice라고

여기는 선택을 하는 것이다

그리고 이 것은 뒤에 나올 problem들의 결정에 대해서

아무런 영향을 주지 않는다

이러한 과정을 반복하면 결국 가장 좋은 결과를

선택할 수 있게 된다