동적 계획법(Dynamic Programming) - 6






이번 시간에는 동적 계획법의 또다른 고전 중에 Knapsack Algorithm에 대해 알아보자

Knapsack은 배낭을 가리키는 말인데 배낭 알고리즘 이라고도 한다.

이 알고리즘에는 재미있는 이야기가 숨어있는데, 

도둑이 상점에 물건을 훔치기 위해 배낭 하나를 들고 왔다고 했을 때,

가지고 나갈수있는 무게가 한정적이지만 최대의 비용을 낼 수있게 해야한다.


각각의 물건 마다 무게와 가격이 다 다르다.

따라서 n개의 아이템과 배낭의 용량 W가 주어질 때

배냥의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합을 구해야 한다..


예를 들어 위의 그림에서 {1,2,5}는 가격의 합이 35,

{3,4}는 가격의 합이 40,

{3,5}는 가격의 합이46 이지만 배낭의 무게를 초과한다.


이런 문제를 어떻게 풀어야할까?

가장 먼저 Greedy한 알고리즘을 생각해 볼 수 있다.

그러나 무겁다고 해서 비싼것도 아니고 가볍다고 싼것이 아니다.

그러므로 단위 무게당 가격(가격/무게)이 가장 쉽게 도출해 낼 수 있는 결과이다.


이것을 계산해 보면 위에서부터 1, 3, 3.6, 3.66.., 4의 단위 무게당 가격을 가지는데,

이 때, 그리디 알고리즘에 의해 2번과 5번을 선택 하게되며 결과는 34가된다.

그러나 이는 최선이 아니다.





그러므로 동적계획법을 사용해서 이 문제를 풀어야한다.

동적 계획법을 사용하기 위해서 먼저 순환식을 세워야한다.

여기서 OPT(i, w)는 배낭 용량이 w일 때 아이템 1,2,3...i로 얻을 수 있는 최대 이득을 뜻한다.

이 때 아이템 i를 선택하는 것에 의해 2가지 케이스로 분기된다.

첫번째는 i를 선택 하지 않는 경우는 i는 제외 되지만 용량은 줄어들지 않으므로 w에 변화는 없다.

다른 경우는 i를 선택하는 경우인데 i도 제외되며 용량도 마찬가지로 줄어들게 된다.






결론적으로 위의 순환식을 가지게 된다.

경우 2를 선택 하기 위해서는 조건이 필요한데, 현재 잔여용량 W가 아이템 i의 무게 Wi보다 커야한다.

이러한 조건이 만족될 경우만 경우 2를 선택할 수 있다.

그리고 i가 0이라는 말은 아이템이 더 이상 남아있지 않음을 뜻한다.






결과적으로 슈도 코드는 위와 같이 표현된다.

2차원 배열을 사용해서 표현되며 때문에 2개의 반복문이 사용되었다.

반복문 내부의 조건 분기는 순환식에서 이미 구한 식이다. 



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


저작자 표시
신고

동적 계획법(Dynamic Programming) - 5






이번 시간에는 Longest Common Subsequence를 알아보자

Longest Common Subsequence는 줄여서 LCS라고 부르는데, 약어로 부르는것은 그만큼 유명하다는 뜻이다.

입력으로 2개의 문자열이 주어지며, bcdb는 문자열 <abcbdab>의 subsequence이다.

또한 <bca>는 문자열 <abcbdab>와 <bdcaba>의 common subsequence(공통 부분 문자열)이다.


우리가 고려해야할 부분은 LCS인데, 입력으로 2개의 문자열이 주어졌을때, 

common subsequence중에서 가장 긴것을 찾으면 된다.

예를 들어, <bcba>는 <abcbdab>와 <bdcaba>의 LCS가 되는 것이다.





그렇다면 위의 그림에서 x라는 문자열과 y라는 문자열이 입력으로 주어진 문자열이며,

z가 우리가 원하는 최적해라고 할 때, z의 일부분이 어떤 부분에 대한 최적해가 되는 것일까.

만약 이 z라는 문자열의 마지막이 A라면 x에도 포함될 것이며 y에도 포함 될 것이다.

그리고 x의 하늘색을 x', y의 노란색을 y'라고 한다면 z의 보라색은 x'와 y'의 LCS가 된다.






L[i][j]는 입력으로 주어진 X와 Y의 LCS의 길이를 뜻한다.

이때, Xi와 Yj가 같은가 다른가에 따라서 2가지 케이스로 분류된다.

만약 Xi와 Yj가 같다면 Xi와 Yj를 제외한 문자열의 LCS를 구한후 마지막 값인 1을 더해준다.





만약 Xi와 Yj가 다르다면 적어도 둘중 하나는 버려야 한다.

다만 문제는 둘중 누구를 버려야 하는지 알수 없다.

먼저 Xi를 버린다는 것은 Xi를 제외한 X전체와 Y의 LCS를 구한다는 것이고,

Yj를 버린다는 것은 Yj를 제외한 Y전체와 X의 LCS를 구한다는 것이다.

따라서 위의 경우 2의 순환식이 성립한다.






종합적으로 보자면 위와 같이 순환식을 정리할수 있다.

i나 j가 0이라는 것은 문자열의 길이가 0이라는 뜻이므로 LCS의 길이는 0이 된다.

그리고 위에서 봤듯이 Xi와 Yj가 같을때와 다를때, 2개의 경우로 나눠서 생각해야한다.






결과적으로 LCS의 코드는 위와 같다.



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



저작자 표시
신고

동적 계획법(Dynamic Programming) - 4





이번에는 동적 계획법 알고리즘에서 가장 유명한 알고리즘인 Matrix chain multiple을 알아보자

이것은 말그대로 두 행렬을 곱하는 알고리즘이다.

위의 코드는 pxq인 A 행렬과 qxr인 B 행렬의 곱하기 이다.

3개의 반복문으로 돌아가며 곱셈 연산의 횟수는 pqr번이고 결과값은 C에 저장된다.


그러나 우리가 지금 하려는 것은 Matrix chain이다. ABCD의 행렬을 차례로 곱해야 하는 것이다.

행렬은 결합 법칙이 성립하므로 계산 순서에 따라서 곱셉 연산의 횟수가 달라진다.

그럼 n개의 행렬을 곱할 때 최적의 순서는 무엇일까




이 문제를 동적 계획법으로 접근할때 어떻게 풀어야 하는지를 생각해보면,

subproblem으로 나눠서 optimal substructure를 확인해야 한다.

따라서 이것은 계산 순서를 찾는 것이므로, 최적의 계산 순서를 가정한 후에 맞는지 확인해야한다.

n개의 행렬을 곱하는 것은 최종적으로 1개의 행렬이 된다.

그리고 1개의 행렬이 나오기 전에는 2개의 행렬이 있다.

그러므로 X와 Y를 곱해서 Z가 되었다면 A1에서 어딘가까지가 X, 어딘가에서 An까지의 곱이 Y가 되는 것이다.


만약 이것이 최적해라면, X나 Y를 구하는 과정도 최적해가 되어야한다.

이는 비교적 단순한 optimal substructure이다.






m[i,j]는 행렬 Ai에서 Aj까지 곱하는 최소 곱셈의 횟수가 된다.

그러므로 i가 j보다 작다면, i에서 k 까지를 최선으로 곱할때의 계산량과 k+1에서 j까지 곱할때의 계산량을 더한다.

마지막으로 그 두개를 곱하는 비용(Pi-1*Pk*Pj)까지 계산해서 더해지면 최소곱셈의 횟수가 나오게 된다.


이것이 순환식으로 올바르게 동작하기 위해서는 base case가 필요한데,

i, j의 간격이 점점 좁아지기 때문에, i와 j가 0이 될경우를 base case로 정의한다.

i, j가 같다는 것은 행렬이 1개만 있다는 것이므로 계산량이 0이다. 따라서 0을 리턴한다.





위의 코드가 Matrix chain multiple에 대한 코드이다.

3개의 반복문으로 인해 시간복잡도는 ø(n^3)이 된다.



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


저작자 표시
신고

동적 계획법(Dynamic Programming) - 3




동적 계획법이라는 것은 순환식과 뗄레야 뗄수 없는 관계이다. 

다시 말해 순환식을 효과적으로 푸는 테크닉이라고 할 수 있다.

따라서 동적 계획법은 다음과 같은 특징을 가지고 있다.


1. 일반적으로 최적화문제 혹은 카운팅 문제에 적용된다.

2. 주어진 문제에 대한 순환식을 정의한다.

3. 순환식으로 Memoization 또는 Bottom up 으로 푼다.


동적계획법은 subproblem을 풀어서 원래 문제를 푸는 방식이다. 그런 의미에서 분할 정복법과 공통점이 있다.

분할 정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않다.

즉 서로 overlapping하는 subproblem들을 해결함으로써 원래의 문제를 해결하는 것이다.





분할 정복법과 동적 계획법의 차이점에 대해서 좀더 자세하게 알아보자

우선 분할 정복법의 대표적인 예인 quicksort이다.

퀵 소트의 경우 피봇을 기준으로 두 부분으로 나뉘며, 오른쪽과 왼쪽이 완전히 disjoint하다.

왜냐하면 오른쪽의 계산 결과가 왼쪽에 전혀 영향을 미치지 않기 때문이다.

이렇게 두개의 subproblem을 해결함으로써 원래 문제가 해결되기 된다.






다음은 동적 계획법의 일반적인 행렬 경로 문제이다.

i,j까지 오는 경로를 구할때 (i-1, j)와 (i, j-1)까지 오는 subproblem들이 구해져야하는데

이들이 서로 disjoint한것이 아니라 영향을 미치기 때문에 분할 정복법과는 다른 모습을 보인다.


어떤 문제의 최적해가 그것의 subproblem들의 최적해로부터 효율적으로 구해질 수 있을 때,

그 문제는 optimal substructure를 가진다 라고 말한다.

분할정복법, 탐욕적기법, 동적계획법은 모두 문제가 가진 이러한 특성을 이용한다.






따라서 최단 경로문제를 볼 때 어떤 거리까지의 최단 거리의 부분 집합은 항상 최단 거리이기 때문에

결과값을 구하는 순환식은 optimal substructure를 표현하게된다.

순환식을 세운다는 것은 동적 계획법의 핵심이기 때문에 그리 간단하고 쉽지않다.

그러므로 순환식을 세우는것에는 스킬이 필요하다.


동적 계획법에 대한 순환식을 세우기위해서는 우선,

내가 지금 구하자고 하는 최적해에 대해서 그 최적해의 일부분이 그 부분의 최적해인가에 대한 질문을 던져야한다.

최단 거리 알고리즘에서 설명했던 것과 동일한 말이다.

이를 기준으로 세우고 식을 점점 발전 시킨다면 올바른 순환식이 도출되게 된다.

참고가 되는 것이 있다면 고등학교 과정에서 점화식 파트를 보는 것도 도움이 될것이다.






optimal substructure를 설명하기 위해 다른 예를 보자

다음은 최장 경로 알고리즘이며, 최단 경로와 반대된 결과를 찾아야한다.

1에서 4까지의 최장 경로는 (1,2,3,4)이지만 1에서 3까지의 최장경로는 (1,4,2,3)이다.

따라서 '최장 경로의 일 부분이 그 부분에 대한 최적해다' 라는 것이 당연히 성립하지 않는다는 것이다.

따라서 위와 같은 순환식은 세울수가 없다.






그러므로 위와 같이 식이 수정되야한다.

S에서 u 까지 A에 속한 원소들과 v 모두를 지나지 않고 도달하는 것을 찾고 최대값을 구한다.

최장 경로 문제에 대해서는 최적해가 그 부분에 해당하는 최적해다 라는 조건이 성립하지 않지만

이 최장 경로 문제가 optimal substructure가 안되며 동적계획법으로 풀수 없는 것은 아니다.

왜냐하면 위와 같이 복잡한 형태, 다른 형태의 optimal substructure를 가지기 때문이다.



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



저작자 표시
신고

동적 계획법(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


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

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




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


저작자 표시
신고

동적 계획법(Dynamic Programming)






우리가 전에 피보나치 수를 계산하기 위해 재귀 함수를 사용했었다.

이는 같은 연산이 반복되기 때문이다.

 그러나 이 함수의 진행 과정을 살펴보면 중복이 심하다는 것을 알수 있다.

위의 그림에서 보면 fib(2)가 여러번 반복되며 오버헤드가 증가함으로 결국 비효율적인 코드가 된다.





따라서 이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다.

이는 사전에는 나오지 않는 프로그래밍 테크닉이며, 계산된 값을 버리지 말고 저장한다는 뜻이다

예를 들어 위의 그림에서 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다.

이렇게 저장되는 배열을 '캐시'라고 하며, 중간에 저장하는 걸 '캐싱한다'라고 부른다.


따라서 위의 그림에서 처럼 배열 f를 캐싱용으로 하나 만들어 둔다.

이 배열 내부를 -1로 모두 초기화 시키고, 만약 -1이라면 결과값이 저장되어 있지 않으므로 계산을 실행한다.

이렇게 되면 어떤 경우에도 동일한 피보나치를 2번 실행하는 경우가 없다.





중복된 계산을 피하는 또 다른 방법으로는 Bottom up 이 있다.

재귀 함수가 Top down 임에 반해, Bottom up은 f(1)부터 f(n)까지 올라 오는 것을 의미한다.

이 방식의 핵심은 아래에서 부터 올라가기 때문에 f(n)을 구하기 위해 f(n-1)과 f(n-2)을 계산해야한다.

따라서 가장 기본적인 값으로 특정한 값을 계산 하려고 하는것을 Bottom up이라고 한다.


이렇게 Bottom up방식으로 계산하는 테크닉을 다이나믹 프로그래밍이라고 한다.

물론, 이는 다이나믹 프로그래밍을 좁은 의미로 해석할때 사용하는 방법이지만

가장 많이 사용되는 방법중에 하나이기도 하다.





두번째 예로, 이항 계수를 구하는 알고리즘이다.

이항 계수는 n개 중에 k개를 선택하는 경우의 수를 구할 때 사용한다.

보통 n!/(n-k)!*k!로 계산을 하지만, 이렇게 할 경우 많은 계산이 중복된다.

또한 계산의 범위가 커질 경우 오버플로우가 생길수도 있다.


때문에 이렇게 하는 대신, 위의 그림의 공식을 사용하도록 한다.

물론 n=k일때거나 k=0일때 1을 반환하도록 한다.

그래서 이를 계산 할 때, 위와 같은 재귀 코드를 사용해서 계산하면 된다.

이렇게 재귀 함수를 반복하다보면 언젠가 n이 k와 같아지거나 k가 0이 되는 base case에 도달하게 된다.

따라서 이항계수의 답을 찾게 된다.






그러나 이와 같은 재귀 계산에서도 같은 값에 대해 중복되는 코드가 많아지므로

메모이제이션 기법을 사용하면 훨씬 빠르고 강력한 계산이 가능하게 된다.

앞서 말한것과 마찬가지로 -1로 모든 캐시 배열을 초기화 해주며,

-1일 경우 계산을 진행하고, 아닐경우 해당 인덱스의 배열값을 호출 한다.





마찬가지로 이를 Bottom up 방식으로 계산을 한다면 위의 그림과 같은 결과가 나온다.

2차원 배열이라서 어디가 Bottom up인지 생각할수 있지만, Bottom up이란 위치가 바닥에서 부터가 아니라

기본적인 값에서 부터 출발한다는 뜻이된다.

따라서, 순환식에서 기본적인 값을 토대로 계속 정답까지 값을 구하므로 재귀가 필요없고 중복된 값도 제거된다.






메모이제이션과 다이나믹 프로그래밍의 특징은 다음과 같다.


1) 메모이제이션이나 다이나믹 프로그래밍 둘다 순환식을 계산하는 방법이라고 할 수 있다.

2) 모두 동적 계획법의 일종이라고 보기도 한다.

3) 메모이제이션은 Top down 방식이고 실제 필요한 sub problem을 푼다, 

4) 다이나믹 프로그래밍은 Bottom up 방식이며 재귀에 수반되는 overhead가 없다.




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

저작자 표시
신고

최단경로(Shortest Path Problem) - 2





위의 그림은 Bellman-ford 알고리즘의 예이다.

첫번째 라운드에서 모든 엣지들에 대해서 relax 한다.

relax연산이 끝나면 초기 시작점과 인접한 엣지들의 ∂값이 세팅된다.

이렇게 순차작으로 relax 연산을 실행한다.

위 그림은 한가지 실행 가능한 예이며, 어떠한 엣지를 선택하느냐에 따라서 다른 순서를 가진다.






이 Bellman-ford는 시간 복잡도에서 그리 좋은 알고리즘은 아니다.

위의 그림은 왜 Bellman-ford의 시간 복잡도가 비효율적인지 알려준다.

Bellman-ford 의 최악의 상황이 표현되었고, d[v]가 한번 갱신될때 마다 우측의 노드들의 값이 바뀐다.

이는 불필요한 계산이 증가한다는 것이고, 그에따른 오버 헤드도 증가한다.




다음은 좀 더 효율적인 다익스트라 알고리즘에 대해 알아보자

우선 초기화는 Bellman-ford 알고리즘과 동일하며, 엣지들에 대해 relax를 하는것도 같다.

그러나 모든 엣지들에대해 relax를 하는 것이 아니라 distance값이 최소인 값을 찾는다.

그 후, distance 값이 최소인 노드로 부터 나가는 엣지들만 relax를 실행한다.

이것이 다익스트라의 한라운드이다.


그리고 relax된 노드를 두번 선택할 필요는 없다.

이유는 해당 노드가 가지고 있는 d값이 이미 최단 경로이기 때문에, 다시 갱신할 이유가 없기 때문이다.

결과적으로, 한번 relax를 한 엣지에 대해서는 relax연산을 하지 않는다.






다익스트라 알고리즘의 특징으로 첫번째, 음수 가중치가 없다.

또한 S로 부터 최단 경로의 길이를 이미 알아낸 노드들의 집합 S를 유지한다.

따라서 맨처음에는 출발점만 있기 때문에 S={s}가 된다.

그러므로 모든 노드들의 최단경로의 집합이 S가 된다.


집합 S에 속해있지 않는 노드 u에 대한 d(u)는 

집합 S에 속해있는 노드들을 통해 u까지 갈수 있는 최단경로의 길이다.





위의 그림은 다익스트라 알고리즘의 실행도이다.

앞서 말했던것 처럼 자신과 인접하고 노드에서 나가는 엣지에 relax연산을 실행한다.

이렇게 f까지 연산을 완료하면 모든 노드에 대한 최단 경로가 찾아진다.






위의 슈도 코드는 다익스트라 알고리즘이다. 그 중 6번 라인까지가 초기화를 실행하는 코드이다.

반복문을 n-1번 수행하며 relax 연산으로 모든 노드까지의 최단 경로를 찾는다.

좀 더 자세하게 말하자면 방금 선택한 노드가 u라면 u에서 나가는 엣지에 relax연산을 해준다.

그리고 최단경로를 다시 탐색하여 해당 노드까지의 최단 경로에 넣어준다.

2개의 반복문으로 인해 시간복잡도는 O(n^2)가 된다.



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


저작자 표시
신고

최단경로(Shortest Path Problem) - 1




이번시간에는 그래프 알고리즘 중에서 가장중요하고 유명한 최단 경로에 대해 알아보자

최단 경로는 이름 그대로 가장 짧은 경로를 찾는 것이다.

먼저 최단경로 문제에서는 가중치를 가진 그래프가 주어진다.

사실 최단 경로에서는 방향/무방향이 무의미하다. 따라서 방향 그래프를 예시로 설명을 진행한다.


경로의 길이를 정의해야하는데, 길이는 그 경로상에 있는 모든 가중치들의 합이다.

따라서 최단 경로는 U에서 V로가는 가장 짧은 길이를 말한다.

그러므로 이렇게 U에서 V까지의 최단 경로를 ∂(U,V)라고 정의한다.

최단 경로 문제의 목적은 ∂(U,V)를 구하는 것이다.






최단 경로의 문제의 유형에 따라 구분을 할수 있다.

먼저 하나의 출발 노드로부터 모든 노드의 최단 경로를 찾는 single-source이다.

single-source로 가장 유명한 것이 다익스트라 알고리즘이다.

이는 one to all 최단 경로 알고리즘이라고 불린다.


이와는 반대로 single-destination은 목적지 t가 주어지면 

모든 노드로 부터 목적지 t까지의 최단 경로를 찾아내는 것이다.

만약, 무 방향 그래프이면 이 문제의 해답은 single-source 문제와 같다.


single-pair는 주어진 하나의 출발 노드 s로 부터 하나의 목적지 노드 t까지의 최단 경로이다.

pair라는 말 그대로, 출발 노드와 목적지 노드가 쌍을 이루게 된다.

사실상 현실적으로 가장 효율성, 실용성이 있는 문제가 된다.


All-pairs는 모든 노드쌍에 대한 최단 경로를 찾는 것이다.

다른 이름으로 all-to-all이라고 불린다.

가장 유명한 것이 플로이드 알고리즘이다.







알고리즘을 살펴보기 전에 짚고 넘어가야할것이 음수 가중치이다.

말그대로 가중치가 음수인 상황인데, 거리가 음수인 경우가 없으므로

 많은 최단경로 알고리즘이 음수 가중치(negative weight)가 없다고 가정한다.

그러나 항상 그렇지는 않다. 따라서 음수 가중치가 존재할수 있다는 것이다.


더 나아가서 음수 사이클(negative cycle)은, 모든 경로의 합, 길이가 음수가 나오게 된다는 것이다.

사이클이 돌면 돌수록 길이가 짧아지므로 현실적으로 말이 되지 않다.

따라서 음수 사이클이 있으면 최단 경로가 정의 되지 않는다.






또한 최단 경로가 가지고 있는 가장 기본적인 특성에 대해 알아보자.

당연한 소리일지도 모르지만, 최단 경로의 부분 집합도 부분 집합의 끝에서 끝까지의 최단 경로이다.

결국 최단 경로는 모든 최단 경로들의 합이 되는 것이다.


또한 최단 경로는 사이클을 포함 하지 않는다.

물론 음수 사이클을 가지지 않는다는 조건 하에서 말이다.

사이클을 포함하지 않는 이유는 최단 경로로 가는데 굳이 사이클을 돌아서 갈 필요가 없기때문이다.






최단 경로 알고리즘의 첫번째로 Single Source, One-to-all 문제를 알아보자

출발점을 포함하는 모든 노드들에 대해서 d[v]값을 유지한다.

이는 S로 부터 V까지가는 경로의 최단 길이에 대한 추정치의 의미이다.


처음부터 최단 거리에 대한 것을 모르기 때문에, 노드까지 가는 데이터가 많아지면서

d[v]는 현재까지 찾은 최소한의 경로의 길이가 되며 꾸준히 업데이트된다. 

따라서 d[s]=0로 시작하고, 데이터가 없는 다른 노드들에 대해서는 d[v] = 무한대가 된다.

그러다가 결국 d[v]는 최종적으로 ∂(s, v)가 된다.


그 다음 최단 경로 길이의 문제가 길이만을 구하는 것이 아니라 실제 경로 자체를 구해야한다.

따라서 이를 위해 π[v]를 표현하며, s에서 v까지 최단 경로상에서 v의 직전 노드를 의미한다.

같은 원리로 처음에는 그런 노드가 없으므로 π[v] = NIL이다. 






다음으로 대부분의 최단 경로에서 기본적으로 제공되는 연산이 Relaxation이다.

위의 그림에서 u까지의 최단경로는 d[u] = 5, v까지의 최단 경로는 d[v] = 9가된다.

그런 상황에서 u에서 v로 가는 엣지에 대해서 relax한다는 것은 최단 경로를 최신화 한다는것이다.

즉, 기존에 자신이 알고 있는 경로보다 더 나은 경로를 하나 발견하고 적용한다는 것이다.


(a)의 그림을 보면 d[v]=9였다가 더 짧은 가중치 2의 경로를 발견하고 d[v] = 7이 되었다.

(b)에서는 가중치를 적용하더라도 기존의 값보다 최적화 되지 않으니 적용하지 않는다.

(슈도 코드에서 w란 weight function이며, 모든 엣지들에 대해서 weight를 부과하는 함수이다.)


실제로 대부분의 single source 알고리즘은 relax 연산을 반복적으로 수행함으로써 최단 경로를 찾는다.

알고리즘 간의 차이는 relax 연산을 어떤 엣지에 대해서, 어떤 순서로 하느냐에 따라 발생한다.






위의 슈도 코드는 일종의 기본적인 single-source 알고리즘이다.

일단 첫번째 스텝은, 위에서 언급했듯이 값을 초기화 하는것이다.


다음에 코드를 잘보면 모든 엣지에 대해서 한번씩 relax 연산을 하게 된다.

엣지들이 여러개 이므로, 어떤 엣지부터 반복하느냐가 구체적으로 된다면 알고리즘이 확정된다.

이를 한번하고 끝나는 것이 아니라, 아무 변화가 없어질때 까지 계속 반복해야한다.

변화가 없다는 것은, d[v]값이 업데이트 되지 않을 때, 최단 경로가 안정화 되었을 때를 의미한다.






위의 그림을 잘 살펴보면 앞서 본 2개의 질문에 대해 대답할 수 있다.

결론부터 말하자면 n-1의 반복으로 충분하다는 것인데 왜 이런 횟수가 나온걸일까.


우선 노드가 n개 일 때 엣지의 최대 개수는 n-1개가 된다.

왜냐하면 최단 경로는 사이클을 포함하지 않으므로 노드를 2번 지나갈수 없다.

따라서 모든 노드를 거치더라도 엣지의 개수는 n-1개가 된다.


따라서 모든 엣지들에 대해 relax를 하는 것을 한 라운드라고 할 때, 첫번째 라운드에서 d[v1]은 찾아진다.

왜냐하면 첫번째 라운드에서 모든 엣지들에 대해 relax를 하기 때문에, 

v1노드 까지의 최단거리는 확정된다. 


그리고 두번째 라운드에서 v2 까지의 최단 경로가 찾아지며

세번째 라운드에서는 v3 까지, i 번째 라운드에서는 d[vi]까지의 최단 경로가 찾아진다.

그리고 위에서 말한 엣지의 개수는 n-1개 이므로, n-1번의 반복으로 최단 경로가 찾아진다.





사실은 이렇게 반복하는 것이 Bellman-ford 알고리즘이며 슈도 코드는 위와 같다.

앞서 살펴본 일반적인 알고리즘과 다른 점은 for문의 반복이 n-1로 고정 되어 있는 것이다.

또한, Bellman-ford 알고리즘은 음수 사이클이 있는 경우에도 이를 탐지 할 수 있다.



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


저작자 표시
신고

최소비용신장트리(Minimum Spanning Tree) - 4




이번에는 두번째 MST인 프림의 알고리즘에 대해 알아보자

프림의 알고리즘도 마찬가지로 안전한 엣지를 하나씩 추가함으로 완성되는데

안전한 엣지를 찾는 방법이 크루스칼의 알고리즘과 다르다.


프림의 알고리즘에서는 먼저 출발점인 노드를 선택해야한다.

그리고 그 출발점인 노드에서부터 점점 몸집을 키우기 시작한다.

즉, 출발 노드에서 인접한 노드를 선택하고, 여기서 나가는 엣지를 하나 선택하고, 이를 반복한다.

크루스칼에서는 떨어진 노드들을 선택했는데 프림의 알고리즘은 인접한 노드를 선택하는것이 차이점이다.


이 때, 어떤 엣지를 선택하느냐에 대한 방법을 알아봐야하는데,

매 단계에서 트리에 포함되어진 노드와 포함되지 않은 노드 사이에 가중치가 가장 작은 엣지를 선택한다.







먼저 출발 노드를 선택하는데 아무 노드나 선택하면 된다.

위의 그림에서는 노드 a를 선택했다.

a와 인접한 노드는 b 와 h가 있는데, 둘 중에 b와 연결된 엣지의 가중치가 낮으므로 b와 연결해준다.

같은 원리로 c와 h중에 c와 연결된 엣지의 가중치가 낮으므로 c와 연결해준다.

동일한 방법으로 노드 i와도 연결된다.

이를 반복해서 결국 엣지가 n-1일때까지 반복을 하면 MST가 완성된다.





위의 코드는 프림의 알고리즘에 대한 슈도 코드이다.

우선 출발점을 0으로 설정해주고 while문으로 엣지가 n-1일때까지 반복한다.

그리고 while문안에서 최소값을 찾아 Va에 포함시키고 

u에 인접하면서 Va에 속하지 않은 각각의 값에 대해 key값을 갱신한다.


이 때 while 문은 n-1번 반복되며, for 문에 의해 키값이 갱신되므로

시간복잡도는 O(n^2)으로 표현된다.




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


저작자 표시
신고

최소비용신장트리(Minimum Spanning Tree) - 3





저번 시간에 이어 크루스칼의 알고리즘을 계속 진행한다.

크루스칼의 알고리즘을 위해서는 원소 u가 속해있는 집합이 무엇인지 찾을수 있어야하고(Find) 

2개의 집합을 하나로 합치는 연산(Union)을 지원해야한다. 이를 Union Find Problem이라고 한다.


결론을 이야기하면 Union Find Problem을 해결하기 위해, 각각의 집합을 하나의 트리로 표현해야한다.

이 때, 이러한 트리에 규칙이 없다. 이진 트리도 아니고 자식이나 부모에 대한 규제도 없다.

대신 해당 집합의 모든 원소들이 트리의 노드로 들어가야한다는 것이다.


또한 일반 트리가 밑으로 내려가는 것과 달리, 여기서는 루트 노드까지 올라가는 연산, 즉 상향식 트리이다.

이것의 의미는 트리의 각 노드가 자기 자식 노드의 주소를 가질 필요가 없고, 

자신의 부모가 누구인지에 대한 정보만 가지면 된다.

이것은 꽤 중요한 정보인데, 유일한 부모 노드의 정보만 가지기 때문에 복잡성을 낮출수 있게된다.


정리하자면 서로소인 집합을 표현하기위해서 상향식 트리로 표현한다는 것이다.

또한 모든 노드는 부모를 가지고 있어야하므로 어떤 노드의 부모가 자기 자신일때 루트 노드이다.

이를 통해서 알고리즘을 좀더 간단하게 만들 수 있다.







예를 들어서 위의 그림은 크루스칼의 알고리즘이 진행되는 시점인데,

현재까지 선택된 엣지들이 파란색 선이라면 4개의 집합이 존재한다.

실제 프로그램 안에서는 4개의 집합을 각각 1개씩의 트리로 표현하므로 총 4개의 트리로 존재하게 된다.






이렇게 상향식 트리로 만들어진 경우 모든 트리를 하나의 배열로 표현할 수있다.

이것이 크루스칼의 알고리즘을 상향식 트리로 만드는 가장 큰 이유이다.

여기서 배열의 인덱스는 노드를 의미하며, 인덱스 내부의 변수값은 부모를 나타낸다.

실제 프로그램안에서는 a,b,c보다 숫자로 표현되게 될것이다.

이렇게 표현 할 수있는 방법은 부모가 유일하기 때문이다.

반대로 생각해서 자식을 표현하게되는 경우 자식은 여러개이므로 복잡하게 표현이 된다.





1
2
3
4
5
6
Find-Set(x){
    if(x!=p[x]){
        then p[x]<-Find-Set(p[x])
    }
    return p[x]
}
cs


본격적으로 크루스칼 알고리즘에서 사용되는 코드들을 알아보자.

앞서 설명한 슈도 코드에서 사용되는것은 Find와 Union 이었다.

이중 Find는 어떤 두 노드가 같은 집합에 포함되는지를 알아보는 연산이었다.

이를 위해 두 노드의 루트 노드가 동일하면 같은 집합에 있다고 판단한다.

따라서 find의 결과는 루트 노드의 이름을 리턴해주게 된다.

위의 코드는 Find-Set를 재귀로 구현한 코드이다.


이 find-set의 시간 복잡도를 생각해보면, 트리의 아래에서 부터 루트노드까지 찾아올라가므로

O(h)의 시간복잡도를 가지며 여기서 h는 트리는 높이 이다.

만약 트리를 잘못 만들면 모든 노드들이 1열로 줄서 있으므로 최악의 경우 시간 복잡도는 O(n)이 된다.






두번째는 Union인데 두개의 집합을 합집합으로 만드는 연산이다.

예를 들어 위 그림에서 c가 루트인 트리와 f가 루트인 2개의 트리를 하나로 합치는 것이다.

이를 위해 가장 간단한 방법은, 어느 한쪽 트리가 다른쪽 트리의 자식 트리가 되는 것이다.

따라서 Union을 하는데 걸리는 시간은 루트를 찾아야하므로 find연산과 동일하고,

루트 노드를 찾은 이후에는 둘중의 한명을 다른쪽의 자식으로 넣어주면 되므로 O(1)이다






위의 Union의 알고리즘은 아무생각없이 간단하게 짠 알고리즘이다.

그러나 트리의 높이에 비례해서 복잡도가 증가하므로 가능한한 트리의 높이를 낮춰야한다.

따라서 weighted union으로 합집합을 만드면 복잡도를 낮게 할수 있다.


weighted union의 원리는 간단하다.

트리의 높이를 가능한 낮게 유지한다는 원리에서 작은 트리를 큰 트리의 자식으로 놓는 것이다.

이렇게 되면 전체 트리의 높이가 증가하지 않게 된다.



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

저작자 표시
신고

+ Recent posts

티스토리 툴바