[Dynamic Programming] Maximum Subarray & Floyd Warshall Alg

Maximum Subarray

• Find the consective subarray with maximum sum 합이 최대가 되는 연속되는 서브 배열을 찾아라
• O(\(N^3\)) is easy : sub array의 갯수가 n*(n+1) / 2개가 존재한다.
• O(\(N^2\)) is kind of easy : 연속인 subarray는 시작과 끝 점으로 존재함. 즉 \(_{n+1}\)C\(_2\)개의 subarray가 존재한다.
• O(N)?
• Do we allow subarray with zero elements?

만약 전부 양수 : 배열 전체 (자기 자신도 부분 집합이라고 생각한다)

 

O(\(N^2\))에서 보면, 

이전에 구해둔 배열의 합에서 다음 것만 더하면 됨 => i~j 까지 더하는 과정이 O(1)로 줄어들게 됨

 

이러한 방법은 사이즈가 0인 배열을 고려하지 않는다.

입력 배열이 모두 음수인 경우에 사이즈가 0인 배열이 가장 작다. (풀이는 같은데 답이 달라질 수 있음)

 

ex) 사이즈가 2개인 배열의 합에 + x를 하면 사이즈가 하나 늘어난 합이 됨

ex) 1개의 배열은 그러면 사이즈가 0인 배열에 + y를 하여 사이즈가 1인 sum이 y가 된다. 

 

size가 0인 것을 허용하지 않는 경우, 이런 경우 음수가 나온다면, 이를 0으로 바꾸면 사이즈가 0인 배열의 합과 같아진다.

 

Idea 1

Compute the maximum subarray ending at element i

i번째에서 끝나는 가장 큰 subarray를 알고 있다고 가정하자

i

i+1

 

i 번째와 바로 앞 부분을 포함하는 두 칸이 maximum subarray임을 알고 있다.

i 번째를 기준으로, 1,3,4칸 보다 2칸이 가장 큰 값이라는 것이다.

 

즉, i를 기분으로 1,2,3,4칸이 있는 것에서 i+1 칸을 추가하는 것이다.

i+1을 마지막으로 보았을 때, 가장 maximum인 값은 총 3칸인, i-1, i, i+1이다. (i-1, i가 가장 크기 때문이다)

 

size가 1개 이상인 경우

A[1], A[2], ... A[n]이 온다고 치자

S[1] = A[1]

S[i] = max (S[i-1] + A[i], A[i])

 

size가 0개 이상인 경우

S[0] = 0

S[i] = max (S[i-1] + A[i], 0)

 

Idea 2

• Compute 2 values for each i
  • Max subarray that contains element i
  • Max subarray that may not contain element i
• size 1 이상만 허용

1. i 번째 칸을 포함하는 것 중에 가장 큰 것 (왼쪽에서부터)

2. i 번째 칸을 포함하지 않는 것 중에 가장 큰 것 (붙어있지 않을 수도 있고, 붙어있을 수도 있음)

두 개의 답이 같을 수도 있다.

 

1 은 idea 1의 아이디어와 같다. max(p,q) 

2는 max(s, max(p,q))

 

Idea 3

• Use Prefix Sum

prefix sum : 앞 부분의 합

\(P_1 = A_1\) 

\(P_2 = A_1 + A_2\) 

... 

\(P_{i+1} = P_i + A_{i+1}\)

 

 

i 한칸 : \(P_i - P_{i-1}\) 

i 포함 두칸 : \(P_i - P_{i-2}\)

...

전체 : \(P_i - P_0\)

 

i 번째를 포함하는 가장 큰 값을 찾는 것이기 때문에

빼는 값이 가장 작으면 됨

 

즉, prefix sum의 minimum을 계산하면 된다. 

 

---

All-Pairs Shortest Path

모든 쌍에 대한 Shortest Path

• Given a Weighted Graph
• Find the Shortest Path between all possible Pairs of Nodes
• One Option : Fun Dijkstra N times -> O(nmlogn) *O(m+nlogn) -> O(mn + n2logn)

지금 설명하려는 알고리즘은 O(\(N^3\))이다. 

왜 다익스트라를 사용하지 않는가? n이 엄청나게 크지 않은 한, 지금 설명하려는 알고리즘이 빠르다

 

Floyed Warshall Algorithm

Idea

• (Nodes are Numbered from 1 to N) -> 노드 번호는 그냥 번호일 뿐이다. 그저 이름일 뿐
• Find Shortest Path from (all possible) i to j going through only the nodes in {1,2,3, ... k}
• Do the above by increasing k from 0 to N

k = 0일 때를 활용하여 k = 1일때를 계산.. 같은 방법으로 k = n일때까지 계산

결국 지나는 집합이 {1,2,3, ... n}이 될 때 정답이 될 것이다.

즉, {1,2,3 ... k}만 거치는 shortest path는 정답보다 크거나 같을 것이다.

 

• D[k][i][j] will contain the desired shortest path length
• Calculate D[k][i][j] from D[k-1][i][j]
• Initial values will be in D[0][i][j] : 다이렉트 엣지

 

Shortest Path from i to j using nodes in {1,2, ... k}

• May use node k
• Or may not use node k
• The shorter of the 2 is the answer

둘 다 계산해보면 둘 중 어떤 것이 답인지 알 수 있음 

즉, 배열의 "해"는 k를 사용하는 경우와 쓰지 않는 경우 중 작은 것이다

이미 가장 짧은 이전의 것을 알기 때문에 두가지를 모두 계산할 필요는 없다

 

k를 사용하지 않는 경우 D[k-1][i][j]

k를 사용하는 경우 D[k-1][i][k] + D[k-1][k][j]

 

Q)k가 두 번 나올 수 있는가?

A)불가능하다. k가 두번 나오면 shortest path가 아니기 때문에 가운데 도는 부분을 없애야한다.

 

만약 k = i라면? 자동으로 1,2 케이스가 같아진다.

1번 케이스의 경우 D[k-1][i][j] = D[k-1][k][j]

2번 케이스의 경우 D[k-1][i][k] + D[k-1][k][j] = 0 + D[k-1][k][j]

이기 때문에 알고리즘에서 자동으로 두 개가 같아짐을 확인할 수 있다.

 

int D[n+1][n+1][n+1];

int F(int W[n+1][n+1], int n){
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)    
            D[0][i][j] = W[i][j];
    
    for(k = 1; k <= n; k++)
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j]);
}

 

3차원 배열을 사용하며 메모리를 너무 많이 사용하고 있다.

지금 k에서는 k-1만 가져다가 쓰기 때문에, 모든 것을 기억할 필요 없으므로, 2개의 2차원 배열만 사용할 수 있다.

 

int D[2][n+1][n+1];

int F(int W[n+1][n+1], int n){
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)    
            D[0][i][j] = W[i][j];
    
    for(k = 1; k <= n; k++)
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                D[k%2][i][j] = min(D[(k-1)%2][i][j], D[(k-1)%2][i][k] + D[(k-1)%2][k][j]);
}

 

2차원 메모리의 있는 값들을 그냥 업데이트 해도 괜찮음

그렇지만, 지금 사용하는 값이 업데이트 된 값인지 아닌지 보장이 없음

 

int D[n+1][n+1];

int F(int W[n+1][n+1], int n){
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)    
            D[i][j] = W[i][j];
    
    for(k = 1; k <= n; k++)
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
}

업데이트 된 값이여도 괜찮음

왜냐하면 D[k][i][k] = D[k-1][i][k]가 항상 성립한다.

왜냐하면 k까지 사용하지만 i부터 k까지 계산이기 때문에 현재 path에는 어짜피 k가 나오지 않는다.