[궁극의 웰노운 알고리즘] 9. SMAWK, min-plus convolution(convex and convex), min-plus convolution(convex and arbitrary)

 사실, 이 글의 독자들은 내가 굉장히 자주 주제들만을 적어두고 나중에 채워야 할 글들을 유기하고 있다는 사실을 알 가능성이 꽤 있다. 이러한 부분에 대해서는 굉장히 미안하지만, 일부 주제들의 경우에는 채워지는데에 굉장히 오랜 시간이 들 수 있음을 미리 전한다. 아마도 생각보다 적을 것이 너무 적고 이미 내가 알던 것이거나, 혹은 50장짜리 논문처럼 이해하기에 심히 난해한 알고리즘들이 그러한 경우에 속할 것이다... 아무튼 이번에 다룰 알고리즘들은 최근에 문제를 풀면서 굉장히 깊은 인상을 받았기 때문에 아마도 글이 처음부터 완성본으로 올라갈 것으로 예상된다.

[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution - Codeforces

[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution - Codeforces

해당 글은 내가 이 글에서 다룰 알고리즘들을 배울 때 적극적으로 참조한 글이다. 읽어보면 분명히 이해하는데에 도움이 될 것이다.

 

 

1. SMAWK

사실, SMAWK 알고리즘 그 자체만으로는 사용처가 그렇게 많지 않은듯하다. 왜냐하면, 해당 알고리즘이 풀고자 하는 문제는 naive한 솔루션의 시간복잡도가 입력의 시간복잡도와 동일하기 때문이다! 따라서 SMAWK를 직접적으로 적용하는 문제가 그렇게 많지 않은것은 무리가 아니다. 해당 알고리즘을 이 글에서 설명하는 이유도 후술할 min-plus convolution을 다루기 위함이다...

 

 아무튼, 우리가 해결하고 싶은 문제는 다음과 같다:

 

\(N*M\)인 totally monotonic한 행렬이 주어진다. 이때, 각 행들에서 최솟값을 구하라.

 

앞서 말했듯이, 행렬의 원소는 \(NM\)개이므로 입력의 시간복잡도는 \(NM\)이다. 그리고 알고리즘 문제해결에 어느정도 숙달이 된 독자라면 위의 문제를 \(O(NM)\)에 해결할 수 있다는 사실을 알 것이다. 그렇기 때문에 이 알고리즘이 적용되는 케이스는 대체로 어떤 행렬의 원소를 "직접 계산 가능한 경우"가 된다.

 

아무튼, 사실 해당 알고리즘에 대해서 자세히 다루고자 해당 글을 쓰는 것은 아니며, 굉장히 직관적으로 설명을 해준 참고자료가 있기 때문에 이를 첨부하고 간단히 요약하며 넘어가겠다.

monge.pdf

0.10MB

 

 아무튼, 해당 알고리즘의 요지는 다음과 같다:

1. 만약 \(n<m\)이라면, "reduct"라는 공정을 거쳐서(이는 선형대수학에서 reduced row echelon form을 만드는 공정과도 비슷하다), \(m<=n\)인 문제로 치환한다. 시간복잡도는 아마도 \(O(n+m)\).

2. 그렇지 않다면, 행들을 적절히 뽑아서 부분문제를 푼 뒤, 이를 통해 전체문제를 적당히 해결한다(부분문제에서 얻은 해들로 인해 이루어지는 path 위에 답이 존재하기 때문에, 확인해야 하는 원소들은 기껏해야 \(O(n+m)\)개이다.)

 

중요한 것은, 1 혹은 2가 실행되었을 때 문제의 크기(=N+M)은 1/4 이상 줄어든다는 것이다. 따라서 문제의 크기가 지수적으로 감소하기 때문에, 전체 시간복잡도는 \(O(N+M)\)이 된다. 

 

사실, 이 알고리즘을 이해하는 것이 그렇게 중요하지는 않다. 그냥 일종의 블랙박스처럼 이해해도, 최소한 이 글 내에서 이루어질 추후의 논의에는 아무런 지장이 없을 것이다.

 

2. min-plus convolution(convex and convex)

이제, 조금 더 본격적인 주제에 대해 다루어보겠다. 일단 해당 블로그에서는 앞서 convolution들에 대한 다양한 알고리즘들을 소개한 바가 있다. 그러나, 이러한 것들은 전부 인덱스의 연산을 일반화하여 정의되는 convolution이었다. 지금 다룰 min-plus convolution의 경우에는 인덱스는 기존의 덧셈을 따라가되, convolution을 구성하는 곱셈과 덧셈이 각각 덧셈과 min으로 바뀐 것이라고 볼 수 있다. max convolution도 똑같은 방법으로 풀리기 때문에, 이 글에서는 max convolution을 다루겠다.

 

 아무튼, 2번과 3번을 포괄해서 우리가 풀고 싶은 타입의 문제는 다음과 같다: 

 

 어떤 길이 n,m의 배열 a,b가 주어진다. k=2,...,n+m에 대해서, 각각 다음을 계산하라:

 i+j=k인 i,j에 대해서, a[i]+b[j]의 최솟값

 

 얼핏 보기에 굉장히 간단한 구성의 문제고, 그렇기 때문에 여차저차 풀릴 것이라고 기대해볼 수도 있겠지만, 안타깝게도 해당 문제를 서브제곱만에 풀 수 있는 방법은 아직까지 알려지지 않은 것으로 알고 있다...

 

 그러나, 만약 a,b가 조금 더 특수한 조건을 만족한다면 문제를 효율적으로 해결 가능하리라고 기대해볼 수 있다. 이 문단에서 다룰 것은 a,b가 둘다 convex한 경우 이 문제를 해결하는 방법이다.

 

 사실, 이 문제를 해결하는건 무-척이나 단순하다. a가 convex하다는 것은, 다시 말해서 인접한 두 원소의 차로 이루어진 배열이 단조감소(물론 단조증가일수도 있지만, 편의상 단조감소라고 하자)한다는 것이다. 그렇다면, 인접한 두 원소의 차를 무게로 가지는 돌덩이들 n개를 정의하자. 같은 방식으로, b에 대해서도 같은 방식으로 돌덩이 m개를 만들자.(돌덩이들의 무게가 어떻게 음수일 수 있느냐에 대한 반박은 받지 않겠다.)

 

 이제, 위에서 만든 총 n+m개의 돌덩이들을 무게가 큰 것부터 나열하자. a,b의 max-plus convolution을 c라고 하면, c[k]의 값은 아주 자명하게도, 돌덩이들중 무게가 큰 k개의 무게의 합보다는 작거나 같아야만 한다. 왜냐하면, c[k]는 결국 어떤 i,j들에 대해서 a[i]+b[j]일텐데, 그렇다면 이것은 어떤 k개의 돌덩이들의 무게의 합일것이고, 그것은 가장 큰 k개의 합보단 작거나 같을 것이기 때문이다.

 

 반면, c[k]는 적어도 가장 무게가 큰 k개의 돌덩이의 무게의 합보다는 크다는 사실도 알고있다. 이는 merge sort의 merge부분을 생각하면 이해하기 쉬운데, 어떤 i,j가 존재해서 a에서 i개, b에서 j개를 가장 크게 고르는 방법중 적어도 하나는 전체 돌멩이들중 가장 큰 k개를 고르는 방법이 될 것이기 때문이다.

 

 이 논의를 통해 알 수 있는 것은, 그냥 돌멩이들을 정렬한 다음에 누적합을 씌워주면 그게 a,b의 max-plus convolution이라는 것이다. 심지어 a,b는 이미 돌멩이들의 크기에 대해 정렬되어 있기 때문에 시간복잡도는 merge에 대응하는 \(O(n+m)\).

 

 내가 한 설명이 아마도 논리적 결함은 없을 것이지만, 이 주제의 본질을 깨우치기 위해서는 minkowski sum에 대해서 이해하는 것을 권장한다. 이러한 방식으로 이해하는 것은 해당 convolution을 다른 관점으로 보여줄 수 있을 것이다.

 

혹시나 내가 minkowski sum을 미리 다루었나 블로그들을 보았는데, 불행인지 다행인지 그렇진 않았던듯하다.

 

 

dp optimization에 대한 소양이 있는 독자들은, 해당 알고리즘이 slope trick과 비슷한 결을 가지고 있음을 눈치챌 수 있었을 것이다. 실제로 이 둘을 구현하는 방법은 굉장히 비슷하다고 생각한다. 아무튼, 해당 알고리즘을 활용하면 다음과 같은 문제를 해결할 수 있다: 8987번: 수족관 3 (acmicpc.net)

 

원래 이 문제는 몇가지 그리디적 관찰을 통해 문제를 해결해야 하지만, 이 문제를 dp로 이해한 뒤 dp식을 관찰하면 이것이 max-plus convolution이라는 사실을 알 수 있고, 따라서 충분한 최적화를 가하면 문제가 해결된다. 

 

 이런 연습문제에서 볼 수 있듯이, 이 아이디어는 dp 문제들에서 의외로 자주 사용되기 때문에 알아두는 것이 좋다.

 

3. min-plus convolution(convex and arbitrary)

 이 주제가 사실, 내가 이 글을 통해 설명하고자 하는 가장 결정적이고 강력한 기술이다. 최근에 나는 다랜디와 개인적인 ps에서 두번 다 해당 아이디어를 통해 쉽게 풀릴 수 있는 문제들을 조우했고, 이 두 문제에 참패당한 뒤에야 이 알고리즘을 알 수 있었다.

 

아무튼, 해당 알고리즘은 결국 2의 연장선이라고 볼 수 있다. 단지 2와 바뀐 것은, convolution하고자 하는 두 배열중 하나가 convex가 아니라 임의의 배열이 주어진다는 것이다. 2번의 아이디어를 보았을 때, 이것이 3번으로 확장되기를 바라기는 굉장히 힘들어보인다. 

 

 상당히 직관적이지 않은 성질을 통해서 li chao tree를 통한 \(O((n+m)log(n+m))\) 알고리즘이 존재하긴 하나, 해당 글에서 다루진 않을 것이다. 해당 글에서 다룰 것은, \(O(n+m)\)만에 문제를 해결하는 방법이다.

 

라고는 하지만, 사실 의외로 풀이는 굉장히 간단하다. 우리는 SMAWK 알고리즘이 \(n*m\)행렬에서 각 행들의 최솟값을 \(O(n+m)\)만에 계산할 수 있다는 사실을 이미 다루었다. 그렇다면, 다음과 같은 \((N+M)*N\)행렬을 생각해보자:

 

\( x_{i,j}=a_{i-j}+b_j \)

 

당연히, 해당 행렬에서 각 행들의 최솟값을 구한다면 그게 우리가 원하는 convolution의 결과임을 관찰 가능하다. 여기에서 매우 놀랍게도, 만약 a가 convex하다면, 이렇게 정의된 행렬 X가 totally monotonic함을 증명할 수 있다. 따라서 SMAWK 알고리즘을 적용하면, a와 b의 max-plus convolution을 계산할 수 있다.

 

 이렇게만 들으면 어떤 상황에서 적용 가능할지 난감해할 수 있다. 가장 간단한 사용예시는, 바로 이것이다: 13058번: Jewel Thief (acmicpc.net)

 

해당 문제를 간단히 요약하자면 무게가 최대 D이고, 가방의 크기가 k인 냅색을 \(O(Dk)\)만에 해결하라는 것이다(물론 \(O(Dk)\)보다 비효율적으로도 풀 수 있고, 사실은 그게 해당 문제의 정해일 것이라고 생각된다.).

어떤 두 냅색의 상태가 존재할 때 이 둘을 합치는 것은 max-plus convolution이라고 이해할 수 있다.

 

그리고, 크기가 전부 동일한 물건들에 대한 냅색결과는 convex하다.

 

따라서 우리는 각 \(1<=i<=D\)에 대해서, 크기가 i인 것들만을 모은 냅색결과를 그리디하게 계산한 뒤, 이를 차례차례 합쳐주면 된다.

 

또 다른 내가 본 문제는, 다음이다: 17677번: 케이크 3 (acmicpc.net)

 

해당 문제의 정해는 사실 조금 더 고도의 자료구조를 사용하지만, 이 max-plus convolution을 블랙박스로 이해하기만 한다면 색다른 풀이를 생각해볼 수 있다.

 

 풀이는 다음과 같다:

먼저, 중요한 관찰을 한다. C에 대해서 정렬한뒤 해당 순서대로 선택하는 것이 최적이라는 것이다. 매우 자명하므로 증명은 생략한다.

 

 이제, 기본적인 아이디어는 다음과 같다:

만약 우리가 분할정복을 하면서, 각 구간에 대해서 다음의 배열들을 관리하면서 올라갈 수 있다면?:

1. 해당 구간에서 가장 V가 큰 k개를 뽑았을 때 V들의 합

2. 해당 구간에서 k개의 케이크조각을 잘 골라서 만들 수있는 V의 합-2*(C의 최댓값)의 최댓값

3. 해당 구간에서 k개의 케이크조각을 잘 골라서 만들 수 있는 V의 합+2*(C의 최솟값)의 최댓값

 

만약 이들을 모든 구간에 대해서 계산한다면, 단지 2번 배열과 3번 배열들중 인덱스합이 m인 것들을 조사하며 그중 합이 최대가 되도록 하여, 모든 구간에 대해 최댓값을 취하면 그것이 전체 문제의 답임을 알 수 있다.

 

 따라서 우리의 목적은 1,2,3을 잘 전파하는 것이 된다. 각각을 분석해보자.

 

1. 가장 V가 큰것들을 뽑는 것은, 해당 배열이 convex함을 의미한다. 어떤 구간을 두개로 분할했다면, mid1=max-plus(l1,r1)과 같이 계산 가능하고, 이때 l1,r1은 앞서 말했듯이 convex하다.

2. 이건 1보다는 조금 비자명하다. 두 가지 케이스로 구분해야 한다.

2-1. 만약 C의 최댓값이 되는 원소를 오른쪽 구간에서 골랐을 경우: 이는 max-plus(l1,r2)와 같이 계산 가능하다. r2가 어떤진 몰라도 적어도 l1은 convex하므로, 이 계산이 빠르게 진행될 수 있다.

2-2. 만약 C의 최댓값이 되는 원소를 왼쪽 구간에서 골랐을 경우: 당연히 이는 literally하게 l2이다.

이제 2-1과 2-2의 배열들을 max취해서 mid2로 설정한다. 이 max과정에서 아마 convexity가 손상되는듯하다.

3. 2번과 동일하다.

 

따라서 1,2,3을 모든 구간에 대해 계산가능하고, 시간복잡도는 \(O(nlogn)\)이다.

이처럼, 생각보다 이 아이디어를 적용 가능한 문제가 많다는점에 나 또한 놀랐고, 약간 한쪽 배열에 임의성을 최대한 많이 끌어모아서 다른쪽 배열이 convexity를 지킬 수 있도록 하는 방식으로 해당 아이디어를 적용할 방법을 모색 가능할 것 같다.

 

4. 소감

보통은 어떤 주제든 한두개는 todo로 남겨두는데, 방금 케이크 3을 위의 방식대로 풀고는 느낌이 와서 전부 작성했다. 애초에 minkowski sum은 정말로 자주 등장하는 아이디어였는데, 이걸 한쪽이 arbitrary한 경우에도 적용가능한건 분명히 강력한 아이디어라고 생각한다.