본문 바로가기
알고리즘 문제풀이

[알고리즘] 동적 계획법(Dynamic Programming) - 2

by 마스터누누 2017. 6. 9.
728x90
반응형

동적 계획법(Dynamic Programming) - 2





지난 시간에 이어서 기본적인 동적 계획법의 예를 알아보자

위의 그림은 정수들이 저장된 nXn의 좌상단에서 우 하단 까지 이동하는 문제이다.

단 이때, 오른쪽이나 하단으로만 이동이 가능하다.

또한 이렇게 이동하면서 지나간 모든 셀들에 저장된 값들의 합이 최소가 되도록 해야한다.


사실 이 문제는 그래프의 다익스트라 알고리즘으로 얼마든지 풀수 있지만 여기에서는 동적 계획법으로 풀어보도록하자

앞선 포스팅에서는 이항계수와 피보나치를 구하는 문제를 보았는데, 거기에서는 순환식 자체가 주어졌다.

그러나 실제로, 대부분의 경우에는 주어진 순환식을 푼다기 보다는 문제가 주어졌을 때, 문제를 풀기위한

순환식을 세우고 이것을 계산하는 과정 전체를 동적 계획법이라고 한다.

다시말해 동적계획법에서 본질적인 영역은 주어진 문제를 풀기 위한 순환식을 세우는데 있다.





다시 문제로 돌아가서 이 문제를 동적 계획법으로 풀기위한 관찰을 해보자.

출발점 1,1에서 부터 임의의 위치 i,j까지 도달하기 위해서는 2가지 방법이 있다.

바로 i, (j-1)를 거쳐서 오거나 (i-1), j 로 오는 방법이다.






이를 고려했을때 1,1에서 출발 했을 때 i,j까지 이르는 최소합은 L[i,j]라고 부르며 위와 같다.

i,j까지 도달하는 방법은 i,(j-1)을 거치거나 (i-1),j 로 오는 방법이라고 했으므로

해당 좌표까지 최소합으로 온 다음 i,j로 오면 그 값도 최소 경로가 되는 것이다.

다시 말해서, 최단 경로 알고리즘에서도 그랬듯이 최단 경로의 부분 집합도 최단 경로가 되는 것이다.


만약 i가 1이거나 j가 1일 경우에는 외길로 판단되므로, 하나의 경우만 적용해서 계산한다.

그렇지 않을 경우는, 위에서 내려오는 경우와 왼쪽에서 오는 경우 중 가장 최소합인 것을 선택하여 현재의 셀과 더한다.





1
2
3
4
5
6
7
8
9
10
int mat(int i, int j){
    if(i==1&&j==1)
        return m[i][j];
    else if(i==1)
        return mat(1,j-1+ m[i][j];
    else if(j==1)
        return mat(i-1,1+ m[i][j];
    else
        return Math.min(mat(i-1,j),mat(i,j-1))+m[i][j];
}
cs


이와 같은 알고리즘에서 슈도 코드는 위와 같다.

방금전에 본 순환식을 그대로 코드로 옮긴 것이다.

물론 이렇게 하면 올바로 계산이 되겠지만, 상당히 비효율적인 코드이다.

왜냐하면 값을 구하기 위해 중복되는 요소가 많이 발생하기 때문이다.

따라서 메모이제이션이나 bottom up 방식을 사용해서 보다 효율적인 코딩을 할 수 있다.





1
2
3
4
5
6
7
8
9
10
11
12
int mat(int i, int j){
    if(L[i][j]!=-1return L[i][j];
    if(i==1&&j==1)
        L[i][j] = m[i][j];
    else if(i==1)
        L[i][j] = mat(1,j-1+ m[i][j];
    else if(j==1)
        L[i][j] = mat(i-1,1+ m[i][j];
    else
        L[i][j] = Math.min(mat(i-1,j),mat(i,j-1))+m[i][j];
    return L[i][j]
}
cs


메모이제이션을 활용하여 보다 개선된 코드가 만들어진다.

메모이제이션 기법에서 항상 사용하듯, 배열로 캐시를 만든다.

이렇게 만들어진 캐시는 -1로 초기화 되며, 조건문은 -1이 라면 캐싱이 안된 상태이므로 연산을 진행하고,

-1이 아니라 다른 값이 들어 있다면 연산 없이 기존에 배열에 저장된 값을 리턴하게 된다.


위의 비효율적인 코드와 비교해 보자면

기존의 코드는 저장 없이 리턴을 바로 하게되는 것이며, 메모이제이션은 캐시에 저장하여 리턴하므로

중복된 계산이 사라지며 깔끔하고 효율적으로 변한다는 것이다.






이제 bottom up 방식을 알아보도록하자.

위와 같이 행 우선으로 계산을 하게 된다면, 필요한 값이 항상 먼저 계산되므로 

바로 순환식 계산에 들어가면 된다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int mat(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==1&&j==1)
                L[i][j] = m[1][1];
            else if(i==1)
                L[i][j] = m[i][j];
            else if(j==1)
                L[i][j] = m[i][j];
            else
                L[i][j] = m[i][j] + Math.min(L[i-1][j],L[i][j-1]);     
        }
    }
    return L[n][n]
}
cs


즉, 위와 같이 for 반복문의 2중 중첩을 통해 2차원 배열을 순환하며, 앞서 설명한것과 같이 행부터 탐색을 진행한다.

따라서 시간복잡도는 반복문의 2중 중첩이므로 O(n^2)이 된다.





그러나 이 문제가 요구하는 것은 경로 합이 아닌 경로 자체를 구하는 것이다.

따라서 위의 그림과 같이 추가적으로 배열을 하나 더 만들어서, 선택된 셀에 대한 정보를 넣는다

선택된 셀이라는 것은, 우리가 최소 합을 구하는데 있어서 위에서 오거나 왼쪽에서 온 셀을 둘중에 하나 선택했다.

즉, 이렇게 선택된 값은 최소값이기 때문에, 우리가 지나온 경로이며, 이 경로를 새로 만든 배열에 저장하면 되는 것이다. 





1
2
3
4
5
6
7
8
9
10
11
void printPath(){
    int i=n,j=n;
    while(P[i][j]!='-'){
        print(i+" "+j);
        if(P[i][j]=="<-")
            j=j-1;
        else
            i=i-1;
    }
    print(i+""+j);
}
cs


이렇게 저장된 경로를 출력하기 위해서는 위의 코드를 사용하면 된다.

이 코드를 실행 할 경우 현재의 위치는 물론, 새로 만들어진 배열의 모든 경로를 출력하게 된다.




출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘


반응형

댓글