[자료구조 및 알고리즘] Dynamic Programming (2)

Maximum sub-array

 

Find the consecutive sub-array with maximum sum

 

이때 subarray란 전체 배열안에 연속된 부분 배열을 의미합니다. 즉, 전체 배열에서 부분 배열의 가장 큰 합을 구하는 문제입니다.

 

만약 배열에 음수가 없다면, 최대 부분 배열의 합은 전체 배열의 합이 될 것입니다.

또한 배열에 양수가 없다면, 가장 큰 음수 하나이거나 조건에 따라서 빈 배열이 가장 큰 부분 배열의 합이 될 것입니다.

 

부분 배열의 길이가 0인 것을 허용하지 않는다면, 가장 큰 음수 하나가 가장 큰 부분 배열의 합이 될 것이고,

부분 배열의 길이가 0인 것을 허용한다면, 빈 배열

즉, 0이 가장 큰 부분 배열의 합이 될 것입니다.

 

이하에 적을 알고리즘은 부분 배열의 길이가 0인 것을 허용한다는 조건입니다.

 

O(N^3)

 

가능한 모든 sub-array를 구해서,

가능한 모든 sub-array의 합을 구한 후,

최대값을 비교합니다.

 

부분 배열의 시작 index를 i라고 하고,

부분 배열의 끝 index를 j라고 한다음,

각 부분 배열에 대해서 합을 구합니다.

 

가능한 i는 최대 N개

가능한 j도 최대 N개

부분 배열의 합을 구하는데 최대 N

 

따라서 O(N^3)에 수행가능합니다.

 

O(N^2)

 

부분 배열의 시작점을 기준으로

누적합을 구하면서 기록해나가면 O(N^2)에 가능합니다.

 

부분 배열의 시작점을 i라고 하고,

부분 배열의 끝점을 j라고 한다면,

 

i가 0부터 N-1까지 진행하면서,

j를 i부터 N-1까지 진행하며 부분 배열의 합을 구하면 가능합니다.

 

따라서 O(N^2)에 수행가능합니다.

 

O(N)

 

IDEA 1.

 

Compute the maximum sub-array ending at element i

 

i번째 index에서 끝나는 sub-array의 부분 배열의 최대 합을 D[i]라고 한다면,

문제가 찾아야할 목표값은 D[]배열의 최대값이 됩니다.

 

D[i]의 값을 안다고 했을 때,

D[i+1]의 값은 다음 두 가지 경우 중 하나입니다.

 

i+1번째 index에 위치한 값이 a라고 하고, D[i] = x일 때:

• x+a ≥ 0 → D[i+1] = x+a
• x+a < 0 → D[i+1] = 0 → i+1번 index부터 sub-array를 다시 시작한다

 

1번 case의 경우는 사실 당연하다.

 

2번 case의 경우,

지금까지 구해왔던 부분 배열의 최대값이 i+1번째 값을 넣게 되면 음수가 될 경우인데,

이럴 경우 앞서 배열의 길이가 0인 경우도 허용하기로 했기 때문에

 

그냥 부분 배열을 초기화하는 것이 더 낫다.

 

+ 추가적으로 배열의 길이가 0인 경우를 허용하지 않는다면, x+a와 a를 비교해야한다.

 

Correctness

 

D[i] = x일 때,

이 x는 부분 배열의 길이가 0, 1, 2 ... 인 i에서 끝나는 부분 배열의 최대임이 보장됩니다.

 

그렇다면 x+a는 부분 배열의 길이가 1, 2, 3 ... 인 i+1에서 끝나는 부분 배열의 최대임이 보장됩니다.

그렇다면 부분 배열의 길이가 0인 i+1에서 끝나는 부분 배열의 최대는 무엇일까요?

 

바로 0입니다. 그렇기 때문에 0과 x+a를 비교해서 최대값이

D[i+1]에 들어가게 되는 것입니다.

 

IDEA 2.

 

prefix sum

 

0번째 index에서 시작해서 누적합을 prefix sum배열에 기록합니다.

또한 prefix min배열을 만들어 누적합의 최소값을 기록합니다.

index	0	1	2	3	4	5	6	7	8...
prefix min	0	-6	-6	-6	-6	-6	-6	-6	-6...
prefix sum	3	-6	0	7	4	7	11	12	5
value	3	-9	6	7	-3	3	4	1	-7

 

이때 prefix min값과 prefix sum값의 차이가 부분 배열의 최대 합이 됩니다.

 

위 예시의 경우는 12 - (-6)으로 18이 됩니다.

 

All-Pairs Shortest Path

 

Given a weighted Graph

Find the shortest path between all possible pairs of Nodes

 

Simple solution is to run Djikstra algoritm N times

but Time Complexity is O(N(N+M)logN)

 

Floyd Warshall Algorithm

 

2024.09.24 - [학교 수업/자료구조 및 알고리즘] - [자료구조 및 알고리즘] #20 - Shortest Path

[자료구조 및 알고리즘] #20 - Shortest Path

다익스트라 알고리즘의 경우 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이다. 그러나 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우는 위 알고리즘을 사용하면 된다.

 

IDEA.

 

Find shortest path from (all possible) i to j going through only the nodes in {1, 2, ... , k}

 

i노드에서 j노드를 {1, 2, ... , k}노드들을 거쳐서 오는 최단거리를 D[k][i][j]라고 한다.

우리가 구해야하는 목표값은 D[N][start][end]가 된다.

 

우선 D[0][i][j]는 base가 된다.

D[0][i][j]는 i노드에서 j노드로 연결되어있는 간선의 가중치가 된다.

 

D[k-1][i][j]로 부터 D[k][i][j]를 도출하는 것이 step이 된다.

 

D[k-1][i][j]에서 D[k][i][j]를 도출하는 것은 두 가지 케이스로 분류할 수 있다.

• 추가된 노드 k를 사용하는 하지 않는 경우
• 추가된 노드 k를 사용하는 경우

 

추가된 노드 k를 사용하지 않는 경우는 쉽다.

D[k][i][j] = D[k-1][i][j]이기 때문이다.

 

하지만 추가된 노드 k를 사용하는 경우,

D[k][i][j]는 k를 사용하는 경우는,

D[k-1][i][k] + D[k-1][k][j]로 생각할 수 있다.

 

따라서

D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])

로 점화식을 만들 수 있다.

 

이렇게 하는 경우 Dynamic table을 유지하는데에

3차원 배열이 필요한데,

 

사실 3차원 배열까지 필요하지 않고,

2차원 배열만 필요하다.

 

D의 첫번째 요소값인 k가 그다지 의미가 없기 때문이다.

즉, k-1이나 k나 계산하는데에는 차이가 없다는 의미이다.

 

min()안에 있는 D[k-1][i][j]는 D[k][i][j]로 바꿀 수 있는데

D[k][i][j]는 min()이 끝날 때 까지 D[k-1][i][j]와 같기 때문이다.

 

또한 min()안에 있는 D[k-1][i][k]와 D[k-1][k][j]도 마찬가지인데,

i에서 k로 이동하는 최단거리나,

k에서 j로 이동하는 최단거리에

노드 k를 사용하나, 사용하지 않나 결국은 똑같기 때문이다.

 

즉, Floyd Warshall 알고리즘만 특이하게

3차원의 Dynamic table을

2차원으로 줄여서 코딩이 가능하다.

 

이는 k, i, j를 반복문으로 돌려야하기 때문에

시간복잡도는 O(N^3)에 해당한다.