09. Dynamic Programming(1)

안녕하세요. 오늘은 Dynamic Programming, 동적계획법에 대해 알아보겠습니다. 정보올림피아드 문제를 접해보셨던 분들은 익숙하실 수 있습니다. 입문하기도 마스터하기도 어려운 문제라고 생각합니다. 입문할 때 쉬운 예시만 접하고 큰 고민없이 받아들이기만 한다면 다른 유형의 문제들은 매우 어렵게 다가오는 알고리즘입니다.

 

보통 컴퓨터학에서 dynamic과 static을 비교하면서 dynamic은 run time에 결정되는 element를 표현할 때 사용합니다. Dynamic과 static은 컴퓨터학에서 중요한 특성 중 하나인데, 동적계획법과는 관련이 없다고 합니다. 

 

09.01. 피보나치 수열

동적계획법을 설명하면서 가장 많이 들고 있는 예는 피보나치 수열입니다. 이를 설명할지 말지 고민을 했는데, 이것만큼 쉽게 이해할 수 있는 예제는 없고 기초를 다지기 위해 제 포스팅을 보시는 분들을 위해서 설명하도록 하겠습니다.

 

피보나치 수열의 점화식은 위와 같습니다. Recursive function을 구현하는 예제에서도 빠지지 않고 등장하는 예제이긴 합니다.

int fibo(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fibo(n-2) + fibo(n-1);
}

로 점화식을 그대로 풀이한 code입니다. 그럼 fibo() function의 호출횟수를 구해보도록 하겠습니다. 위의 code에서 

	count[n]++;

한줄만 추가해도 충분합니다.(잘 생각해보면 이 횟수는 피보나치 수열을 이루고 있습니다.)

 

호출횟수가 상당히 많은데 이는 fibo() function이 호출될 때 계산한 값들도 다시 계산하기 때문입니다. 예를 들면 fibo(4)는 아래와 같은 호출 구조를 가지게 됩니다.

fibo(4)
fibo(3)				fibo(2)
fibo(2)		fibo(1)		fibo(1)		fibo(0)
fibo(1)	fibo(0)

잘 보면 색을 칠해놓은 두 부분이 완전히 동일한 구조를 이루고 있습니다. 한 번 계산해도 충분한 값들을 호출할 때마다 계속 call하고 있어 불필요한 계산을 하고 있습니다. 시간복잡도를 생각해보시면 tree 구조라 O(n^2)임을 쉽게 아실 수 있습니다.(등비수열 공식을 사용해도 쉽게 구할 수 있습니다.) 사실 피보나치 수열의 일반항 또한

지수를 포함하는 식으로 알려져 있습니다. 

 

그래서 memoization이라고 불리는 방법을 사용하기 시작하였습니다. 메모이제이션은 이름에서도 알 수 있다시피 어딘가에 기록해두고 이미 기록해둔 것이라면 그 내용을 그대로 사용하고 기록해두지 않았던 것이라면 계산하여 기록해두는 기법입니다.

int fibo(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    
    if(dp[n] != -1) return dp[n];
    
    dp[n] = fibo(n-2) + fibo(n-1);
    
    return dp[n];
}

dp라는 data structure(DP table)를 배열 또는 벡터로 만들고 초기화를 해줍니다. 보통 기록하기전 계산을 한다고 말씀드렸는데 이 계산으로는 절대 나올 수 없는 값으로 초기화를 해줍니다. 이제 다시 시간복잡도를 계산해보면 O(N)이 됩니다.

fibo(4)
fibo(3)				fibo(2)
fibo(2)		fibo(1)		fibo(1)		fibo(0)
fibo(1)	fibo(0)

반복문을 사용할 수도 있습니다. Coding style에 따라 달라질 수 있습니다. 반복문을 사용해서 풀이한다면 조금 참신한 방법도 가능합니다.

    dp[1] = 1;
    for(int i = 2; i <= N; i++)
        dp[i] = dp[i-1] + dp[i-2];
    printf("%d\n", dp[N]);

가장 단순한 반복문입니다. N보다 작은 피보나치 항의 값들을 통해 f(N)을 계산할 수 있다는 것을 이용하여 차례대로 계산하는 방식입니다. 이때도 알 수 있으시겠지만 항상 중요한 것은 base case(기저 사례)입니다.

    for(int i = 0; i <= N; i++){
        dp[i+2] += dp[i];
        dp[i+1] += dp[i];
    }

반복문을 이렇게 바꿀 수도 있습니다. 시간복잡도가 좋아지면서 시간을 save할 수 있었습니다. 그렇다면 메모이제이션을 사용함으로써 우리가 더 사용한 것은 무엇일까요?

바로 메모리입니다. O(N) size의 공간복잡도를 가지게 되었습니다. 메모리를 사용하지 않는다면요?

자료구조 교과목을 배우셨다면 circular queue에 대해 배우셨을 텐데요. 3개의 element 공간을 두고 2개의 element를 통해 계속 element들을 update시켜주면 됩니다. 피보나치 점화식에서 당장 필요한 값은 2개 fibo(n-1)과 fibo(n-2)였다는 점을 상기시킬 필요가 있습니다. 다른 아이디어들이 있으시다면 댓글로 소개해주세요.

 

 

09.02. 동적계획법과 분할정복

다시돌아와 그럼 동적계획법이 무엇인지 설명해드리겠습니다. 동적계획법은 주어진 문제를 부분문제로 나누어 풀고 그 결과를 바탕으로 주어진 문제를 해결하는 것입니다. (다른 정의는 다음 포스팅에서 소개하겠습니다.) 분할정복과 묘하게 닮았습니다. 차이점은 메모이제이션을 보시면 아시겠지만 분할한 부분문제의 성질입니다. 분할정복에서는 부분 문제들이 겹치진 않았습니다. 모든 경우를 메모리를 사용하며 기록한다는 점에서 그리디 알고리즘에 비해 실행시간은 많이 소요되지만 근사치가 아닌 정확한 값을 구할 수 있다는 장점이 있습니다. 

 

 

09.03. Top-down & Bottom-up

Top-down과 Bottom-up 이야기도 빠질 수 없는데요. Recursive function을 접하거나 사회학에서 들어보셨을 수 있는 개념입니다. 탑다운은 가장 먼저 호출하는 문제가 가장 큰 문제이기 때문에, 바텀업은 가장 작은 문제들부터 답을 구해나가기 때문에 이렇게 불립니다. Recursive function은 점화식이 한눈에 보인다는 점에서 가독성이 좋고 반복문은 function call cost가 절약된다는 장점이 있습니다. Top-down 방식은 큰 문제를 해결하는데 필요한 부분문제만 계산하므로 상황에 따라 큰 문제를 해결하기 전까지 어떤 부분문제의 답이 요구되는지 몰라 모든 부분문제를 계산하는 Bottom-up 방식보다 빠를 수 있습니다. 문제에 따라 접근하기 쉬운 방법을 선택하시면 됩니다.

 

 

09.04. Example

백준 online judge 문제 풀이에서 살펴볼 예정입니다. 학부공부/Algorithm PS_알고리즘 카테고리를 방문하시거나

https://ku320121.tistory.com/category/%ED%95%99%EB%B6%80%EA%B3%B5%EB%B6%80/Algorithm%20PS_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

'학부공부/Algorithm PS_알고리즘' 카테고리의 글 목록

Dynamic Programming tag를 이용하시면 됩니다.

https://ku320121.tistory.com/tag/Dynamic%20Programming

SONGANG

 

 

오늘은 동적계획법이라는 아주 중요하고 자주 마주하게 될 알고리즘에 대해 알아보게 되었습니다. 긴글 읽어주셔서 감사합니다. 댓글로 질문과 오류지적은 언제나 환영입니다.