Viper

Usher - Climax (Solderist remix) by Solderist





Usher's Remix Contest가 있길래 휴가나와서 만들었다ㅋㅋ

일단 난 아직 좋은 소리를 만드는 능력은 부족하니까
구성이랑 Re-Harmonization으로 승부를 보려고 했다
그리고 옛날에 만들었었던 비장의 피아노 멜로디를 이곡에 한번 더 썼음ㅎㅎ

좋은 결과 있기를...

 

가중치 방향그래프에서 한 지점에서 다른지점까지 가는 최단 경로를 찾는 방법엔 여러 가지가 있다. 그런데 간선의 가중치가 양수, 음수가 섞여있을 경우에는 Dijkstra 알고리즘은 쓸 수 없고 보통 Bellman-Ford 알고리즘을 쓰게 된다. 단 이것도 '가중치들의 총합이 음수가 되는 사이클'이 그래프 내에 존재하지 않아야 한다는 전제 조건이 있어야한다. 만약 저런 사이클이 존재한다면 '최단 경로'라는 개념 자체가 없어지기 때문이다(그냥 그 사이클대로 무한히 돌면 경로의 길이는 무한히 작아지게 되니까).

또한, 한 지점에서 다른 지점까지 가는 최장 경로는 주어진 그래프의 간선의 가중치에 -1 을 각각 다 곱해준다음 Bellman-Ford를 돌렸을때 나오는 답에 다시 -1을 곱해줌으로써 얻을 수 있다. 물론 이것도 그래프 간선의 가중치에 -1 을 곱했을 당시에 음수 사이클이 없어야 한다는 가정 하에서 이게 성립한다. 즉, 원래 상태의 그래프에서 '가중치들의 총합이 양수가 되는 사이클'이 없어야 Bellman-Ford를 통해서 최장 경로를 구할 수 있다.

사실 Bellman-Ford는 이름은 거창할지 몰라도 쉽게 말해 그냥 큐 하나랑, 정점 크기만큼의 배열(커팅용)을 만들어놓고 BFS 돌려서 찾는 거랑 다를 바 없으니까 딱히 부담가질 필요는 없다. 이론적인 부분에 확신을 갖고 시작하고 싶다면 Bellman-Ford 알고리즘에 대해 더 공부하면 되는 거고..

그런데 뜬금없이 왜 최단/최장 경로를 구하는 법을 알아야 되나? 이제부터 소개할 Minimum Cost Flow 문제들의 풀이에 쓰이기 때문이다.

 

출발지와 도착지가 있는 방향그래프가 있다. 그래프의 방향간선의 가중치에는 두 종류가 있다 - Cost와 Flow 이렇게.
Cost는 그 방향간선을 따라 이동하는데 드는 비용이고, Flow는 최대 얼만큼의 용량이 그 간선을 따라 흐를 수 있는지 나타내는 값이다.
(이전 포스트에서 소개한 문제들에는 방향그래프의 가중치가 Flow 하나밖에 없었다는걸 주목하길 바란다)

만일 출발지에서 도착지까지 가는 어떤 경로가 존재한다면, 그 경로를 통해 1만큼의 흐름이 흐를 때마다 그 경로상의 모든 Cost의 총합 만큼의 비용을 소비하게 된다.
즉 출발지에서 도착지까지 가는 어떤 경로가 있으면, 그 경로에 포함되는 간선들의 Flow의 최소값 만큼의 흐름이 흐를 수 있으므로, 그 경로를 통해 k * (그 경로상의 Cost의 총합) 만큼의 비용을 소비할 수 있다. 여기서 k는 k = 0, 1, 2, …, (그 경로상의 간선들의 Flow의 최소값) 중 하나이다.

이 경우 출발지부터 도착지까지의 최소(혹은 최대) 비용을 구하는 문제이다.

이런 문제를 Minimum(혹은 Maximum) Cost Flow Problem 이라 한다. 최대 비용을 구할 때에도 그냥 Minimum Cost Flow 라고 쓰기도 한다. 어차피 본질적으론 같은 문제니까.

 

 

Minimum Cost Flow 문제 유형은 크게 출발지로부터 도착지까지의 흐름이 얼마라고 딱 정해져 있는 경우와 그렇지 않은 경우 이렇게 두가지로 볼 수 있다.

전자의 경우 중에서, 정해진 흐름의 양이 그 그래프의 Maximum Flow와 같다면 그 문제를 특별히 Minimum-Cost Maximum-Flow Problem 이라고 하고 줄여서 MCMF라고 하기도 한다.

(여기서 중요한게... MCMF라고 쓰면 통상적으로 방금 말한 Minimum-Cost Maximum-Flow Problem을 가리키며, 이전 포스팅에서 소개한 Minimum-Cut Maximum-Flow theory를 가리키진 않는다. 헷갈리는 사람이 간혹 있다.
Minimum-Cut Maximum-Flow theory는 Minimum-Cut과 Maximum-Flow 이 두 문제가 서로 동치라는 이론을 말하고,
Minimum-Cost Maximum-Flow problem은 출발지로부터 도착지까지의 최대의 Flow를 가지는 경우들 중 Cost의 최소값을 구하는 문제이다.
Cut이냐 Cost냐 단어 하나에 따라 의미는 천지 차이가 된다)

참고로 헝가리안 메소드를 통해 풀 수 있는 모든 문제는 MCMF로도 풀 수 있고,
그래프의 모든 간선의 Cost를 0으로 해놓은 MCMF 문제는 이전 포스팅에서 소개한 Maximum Flow 문제와 동치가 된다.

이제 각 유형에 대해 문제들을 살펴보자.

---------------------------------------------------------------------------------

첫번째 유형 - 출발지로부터 도착지까지의 흐름이 정해져 있는 경우이다. 다음 문제를 보자.

PKU 3422 - Kaka's Matrix Travels
http://poj.org/problem?id=3422

N * N 체스판의 각 칸에 음이 아닌 정수가 하나씩 써져 있다. Kaka는 SUM이라는 변수를 가지고 체스판의 가장 좌측 상단에서 출발하여 가장 우측 하단에 도착하는 여행을 하는데, 다음과 같은 규칙을 만족하면서 이동한다. 처음에는 SUM=0이다.

1. 한번에 오른쪽으로 1칸 혹은 아래쪽으로 1칸 이동할 수 있다.
2. Kaka가 위치한 칸의 숫자를 SUM 값에 더한 후, 그 칸의 숫자를 0으로 바꿔버린다.

Kaka가 여행을 1번 하는 경우, 얻을 수 있는 SUM 값의 최대값을 구하는 것은 어렵지 않다. 이제 Kaka가 여행을 K번 하는 경우 얻을 수 있는 SUM 값의 최대값을 구하여라. 여행을 할 때마다 SUM 값은 누적되며, N은 최대 50, K는 최대 10, 체스판에 써있는 숫자는 최대 1000이다.

입력
첫 줄에 N, K가 들어오고, 다음 N개의 줄에 N * N 체스판에 쓰여진 수가 주어진다.

출력
SUM의 최대값을 출력한다.

입력 예
3 2
1 2 3
0 2 1
1 4 2

출력 예
15

 

--

 

K=1일 경우 그냥 다이나믹으로 풀면 된다. K가 2 이상일 경우 문제가 복잡해진다.

그냥 다이나믹을 K번 돌리면 안되나? 라는 생각이 들 수도 있는데, 그렇게 하면 다음과 같은 입력에서 성.. 아니, 안좋은 사태가 발생한다.

3 2
1 2 6
4 5 8
7 3 1

이 입력을 그냥 다이나믹 K번 돌려서 풀어보자.

첫번째 여행 :
0 2 6
0 0 0
7 3 0  (이 때의 SUM은 19)

두번째 여행 :
0 2 6
0 0 0
0 0 0  (이 때의 SUM은 29)

이렇게 해서 29로 답이 구해지는데,

실제의 답은.. 32이다.

첫번째 여행 :
0 0 0
4 5 0
7 3 0  (이 때의 SUM은 18)

두번째 여행 :
0 0 0
0 5 0
0 0 0  (이 때의 SUM은 32)

 

그렇다면 풀이법을 바꿔보자. 이 문제는 위에서 언급한 첫번째 유형의 문제이다. 즉 출발지로부터 도착지까지의 흐름의 양이 정해진 Min-Cost Flow 문제이다.

우선 다음과 같이 체스판 한 칸을 두개의 정점으로 생각하여 그래프를 구성하자. 그래프의 간선에 써있는 숫자는 왼쪽이 Flow(최대 흐름량), 오른쪽이 Cost이다. 최대 흐름량을 무한대로 잡아야 한다면 그냥 K로 두면 된다. 왜냐면 K번 여행을 할 거니까 그 이상의 흐름은 들어올 일이 없기 때문이다. 위 예에서는 K=2이므로 2로 두겠다.

그리고 SUM에 해당하는 변수를 만들고 초기값을 0으로 해둔다.

다음엔 Bellman-Ford를 통해 다음과 같이 출발지로부터 도착지까지의 Cost합이 최대인 경로를 찾고,

SUM 값에 해당 비용을 더하고, 찾은 경로에 포함되는 간선들의 flow의 최소값 만큼을 각 간선들의 flow에서 다 빼주고, 그만큼 반대 방향의 flow를 생성한다.

이 과정은 이전 포스트에서 자세히 다루었으므로 익숙할 것이라 믿는다. 그런데 다른 점은, 반대 방향으로 생성하는 flow의 cost 값은 원래 방향의 cost값에 -1을 곱한 값으로 설정해준다.

 

이 상태에서 SUM값(그림의 예에서는 19)은 여행을 1번 했을 때의 최대값이다. 이제 이 과정을 K-1번 만큼 더 해주면 된다.

Cost의 합이 최대인 경로를 찾고...

SUM값에 더해주고 경로를 바꿔준다(이 때의 SUM 값은 32).

이 과정을 수행한 후의 SUM 값이 정답이 된다. Bellman-Ford를 사용한 이런 일련의 풀이 과정을 Successive Shortest Path 알고리즘이라고 한다.

위 과정에서 볼 수 있듯 이미 지나온 경로를 '취소'하고 이전과는 다른 해를 구하는 과정은 단순히 그리디한 풀이로는 쉽게 따라갈 수가 없다.

주의점으로는, 위 문제는 두 정점 사이에 여러 개의 간선이 존재하는 경우이므로 인접행렬로 코딩하기엔 약간 애로사항이 있을 수 있다는 것이다.

 

비슷한 문제들을 더 소개한다.

--

PKU 3680 - Intervals
http://poj.org/problem?id=3680

요 문제는 구간의 위치 관계에 따라 점과 점 사이에 간선을 그어야 할지 말지만 잘 설정해주면 나머지 과정은 똑같다.
K와 모든 weight가 다 1일 경우는 유명한 그리디(혹은 다이나믹) 문제가 된다.

--

ACM World Final 2006: 3562 - Remember the A La Mode!
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1563

이 문제가 Min-Cost Max-Flow problem의 좋은 예이다. 여기서는 Min-Cost 및 Max-Cost 둘다 구하라고 되어 있다.

보통 이런 류의 문제에서는 풀이 과정에서 '가중치의 합이 음수(혹은 양수)인 사이클'이 나타나지 않는다. 왜 그런지는 귀류법으로 생각해 보시길 바란다.

만일 그런 사이클이 절대 등장하지 않을거라는 확신이 없어 불안할 경우 쓰는 방법이 있긴 한데 이는 맨 마지막에 소개하겠다.

 

 

-----------------------------------------------------------------------------------

이제 Minimum-Cost Flow 문제의 두번째 유형, 즉 Flow의 양이 정해져 있지 않을 경우를 보자. 이 경우도 딱히 다르진 않다.

최대값을 구해야 된다면 출발지-도착지까지의 경로 중 총 비용이 양수인 경로가 없을 때 까지,
최소값을 구해야 된다면 출발지-도착지까지의 경로 중 총 비용이 음수인 경로가 없을 때 까지 위와 같은 Bellman-Ford를 쓰는 과정을 진행하면 된다.

다음 문제를 보자.

--

제23회한국정보올림피아드(2006.7.14) 고등부 문제 2 - 두부 모판 자르기
http://211.228.163.31/pool/bean_curd/bean_curd.php?pname=bean_curd

문제 내용까지 여기 쓰기엔 여러 개의 그림들도 삽입해야 되서 약간 번거로워서.. 링크를 타고 가서 보길 바란다.

이 문제는 크게 다이나믹과 네트워크 플로우 이렇게 두 가지 풀이법이 있는데, 후자가 시간적 면에서 더 빠르고 머리도 덜 아프다.



이 문제의 다음과 같은 예제 입력에 대한 그래프를 그려보겠다.

입력

3
AAC
FCA
ACB

우선 두부판을 체스판처럼 생각해서 체스판의 까만 칸과 흰 칸을 각각 묶는다는 생각으로 그래프를 아래와 같이 그린다.

간선의 가중치까지 표시하려니 그림이 너무 복잡해질까봐 그림에는 써놓지 않았다. 가중치는 출발지와 도착지에 인접한 간선들은 (1,0)으로, 나머지 간선들은 (1,해당 두 단위두부에 해당하는 가격)으로 각각 설정해 주면 된다.

다음으로, 출발지부터 도착지까지의 경로 중 비용이 최대인 경로를 Bellman-Ford로 찾아서
i) 찾은 비용이 양수라면 답에 더하고 경로를 바꾼 다음 다시 이 과정을 반복하고,
ii) 찾은 비용이 음수라면 더 이상 비용이 양수인 경로는 없는 것이므로 반복을 끝내면 된다.

위 과정을 수행한 뒤 답을 저장하는 변수에 저장돼있는 값이 답이 된다.

 

그렇다면 여기서 몇가지 의문점들을 제기할 수도 있을 것이다.

[의문점 1] 그럼 굳이 매번 비용이 최대인 경로를 찾는 이유가 있나? 그냥 어떤 경로든 비용이 양수이기만 하면 바로 답에 더해주고 경로를 바꿔주고를 반복하면 되는 것 아닌가?

이 의문은 아래 그림 하나로 종결된다.

(비록 이 문제에서 가능한 입력은 아니지만, 문제 풀이 과정에서 충분히 저런 상황이 나올 수 있다)

위의 그림을 언뜻 보면 '올바르지 않은 해를 구할 수도 있어서구나' 라고 이해할 수 있다.

근데 좀더 핵심적인 말로 바꿔보면 다음과 같이 된다 - '합이 양수인 사이클이 존재할 수도 있게 되어서구나'
(이 문제는 Max-Cost를 구하는 것이므로, Cost의 합이 양수인 사이클이 존재하면 안된다)

매번 비용이 최대인 경로를 찾아서 풀이 과정을 반복한다면, 풀이 과정 전체에서 합이 양수인 사이클은 등장하지 않는다 - 왜 그런지는 아까도 언급했듯이 귀류법으로 생각해보면 알 수 있다.

따라서 매번 비용이 최대인 경로를 찾는 것이다.

 

[의문점 2] 이 문제는 MCMF에 해당되는 것 아닌가?

이 의문은 다음 입력 예제를 보면 해결된다.

4
AAAF
AFAF
AAAF
FFFF

위 입력의 경우 정답은 400이지만, MCMF로 풀게 되면 300의 답을 얻을 수 있을 것이다.

이 문제에선 2x1 두부의 개수를 최대로 해야된다는 말이 없으므로 MCMF는 아니고, 위에서 언급한 두번째 유형인 총 유량이 정해져 있지 않은 Min-Cost Flow 문제에 해당되는 것이다.

 

-----------------------------------------------------------------------------------

마지막으로 음수(혹은 양수) 사이클이 절대 등장하지 않을거라는 확신이 없을 경우 쓰는 방법에 대해 언급하겠다. 나도 직접 짜본적은 없지만..

Bellman-Ford를 돌릴때에 음수 사이클이 존재한다면 알고리즘이 제대로 동작하지는 않지만, 그 음수사이클이 어떤 건지 찾아낼 수는 있다.
만약 그렇게 찾아낸다면, 그 사이클을 쭉 한바퀴 돌면서 간선들의 Flow의 최소값 만큼의 흐름을 다 역방향으로 해주면 된다. 이때 이에 드는 비용도 답 변수에 더해 주어야 한다.

이 과정을 Cycle-cancelling 알고리즘이라 한다.

Cycle-cancelling을 통해 음수 사이클을 없앴다면 Successive Shortest Path 과정을 계속 진행하면 되고, 사이클이 또 생기게 되면 위 과정을 다시 수행해주면 된다.

이에 대한 이론적인 부분은 다음 링크의 Cycle-cancelling 파트를 참고하길 바란다.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow2
(위 링크는 TopCoder에 어떤 사람이 쓴 Min-Cost Flow Problem 설명인데, 3개 part 중 Part 2의 링크이며, MCF의 이론적인 부분에 대해 더 공부하고 싶은 분들은 Part 1부터 차례로 보시면 될 듯 하다)

 

--

이상으로 네트워크 플로우 설명을 마치겠다.

필자가 직관적인 걸 좋아하나 엄밀한건 그리 좋아하지 않아서, 용어의 정의 및 설명이 명확하지 않거나 틀릴수도 있는데 그런 점이 보이면 가차없는 댓글 부탁드린다.

네트워크 플로우는 시작점과 끝점이 있는 방향그래프에서의 "흐름"에 초점을 둔 문제 접근 방식이다. 여기서 시작점은 그 점에서 다른 정점으로 나가는 간선만 있는 점이고, 끝점은 그 점으로 들어오는 간선만 있는 점이다. 여기 올리는 네트워크 플로우 관련 포스팅들에는 엄밀한 증명 같은 이론적인 부분은 생략하도록 하겠다.

네트워크 플로우는 단순한 그리디로 풀기엔 곤란한 문제를 쉽게 풀 수 있게 해준다. 간단한 예로 다음 문제를 보자.

----------------------------------------------------------------------------------------------------------------

http://211.228.163.31/pool/stall/stall.php?pname=stall

농부 존은 최신 기술을 접목해서 새로운 축사를 지었다. 그러나 기계적인 문제로 모든 축사가 동일하지는 않다.

처음에는 임의로 소들의 우리를 배치했더니 , 어떤 소들은 특정 우리에서는 젖을 생산하지 않았다. 그래서 이때 까지의 데이터를 수집해서 각 소들이 좋아하는 우리 번호를 알수 있었다.

한 우리에 한 마리의 소만이 할당될 수 있고 , 한마리의 소는 한 우리에만 들어 갈 수 있을 때 최대 매칭 수를 구하는 게 문제이다.

입력 형식
첫 라인은 두 개의 정수 N (0 <= N <= 200) and M (0 <= M <= 200)이 주어진다.
N 은 소 마리수이고 M 은 소 우리의 수이다. 다음 N 라인에는 각 소들이 좋아하는 우리 수가 주어진 후 우리 번호가 주어진다.

출력 형식
최대 매칭 수를 출력한다.

입출력 예

입력

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

출력

4

 

 

그리디로 이 문제를 짠다면 데이터에 따라 AC를 받을 수도 있겠지만 뭔가 완벽한 풀이라는 확신이 없어 찝찝함이 남을 수도 있을 것이다. 이 문제를 네트워크 플로우로 접근하여 푼 풀이를 아래에 소개한다.

 

쉬운 설명을 위해 다음과 같은 입력에 대해 풀이를 하겠다.

3 3
2 1 2
2 2 3
1 1

우선 N+M+2개의 정점을 만든다. N개의 정점은 각각의 소들, M개의 정점은 각각의 소 우리들에 해당한다. 남는 두 정점중 하나는 시작점, 나머지 하나는 끝점으로 하여, 시작점에서 각각 N개의 소들에 해당하는 정점들을 향한 방향간선 N개를 만들고, 마찬가지로 M개의 우리들에 해당하는 정점들 각각에서 끝점을 향한 방향간선 M개를 만든다. 그리고 어떤 소에 대해 그 소에 해당하는 정점으로부터 그 소가 좋아하는 우리에 해당하는 정점들을 향한 방향간선을 다 긋는다.

아래 그림에서 하늘색이 소에 해당하는 노드이고, 노란색이 소 우리에 해당하는 노드이다.

방향그래프가 완성되었다. 이제 답을 구하기 전의 마지막 준비로 s 라는 변수를 만들고 초기값을 0으로 설정해두자.

이제 이 방향그래프에서 시작점에서 끝점으로 가는 경로를 찾는다(BFS로 찾는게 신상에 좋을 것이다).

찾았다면, s값을 1 증가시킨다. 그리고 찾은 경로를 다시 끝점으로부터 시작점까지 쭉 거슬러 올라가면서 경로에 포함된 간선들의 방향을 모조리 반대 방향으로 바꿔버린다. 즉, A→B 인 간선이 찾은 경로상에 있으면 A←B 로 바꾼다.

다 바꿨다면 다시 경로를 찾는다. 찾았다면 s를 1 증가시키고 그 경로의 방향을 다시 반대로 바꾼다. 이 과정을 시작점에서 끝점까지의 경로가 더 이상 존재하지 않을 때까지 반복한다.

(현재까지 s값은 2)

(현재까지 s값은 3)
이제 더이상 경로가 존재하지 않으므로 반복을 멈춘다.


위 과정이 다 끝난 시점에서의 s값(이 예에서는 s=3) 이 문제에서 원하는 답이 된다.

물론 구체적으로 어떤 소가 어떤 우리에 들어가면 되는지에 대한 예도 찾을 수 있다. 위 과정이 끝났다면 끝점에서 시작점으로 가는 길이 3짜리 경로가 s개 존재할 것이고, 그 경로 각각을 따라가면서 경로상에 있는 소와 소 우리를 짝지어주어 s개의 (소, 우리) 순서쌍을 구해낼 수 있다.

위 그림에서 각각의 보라색 경로를 따라가면 어떤 소를 어느 우리에 집어넣어야 하는지 알 수 있다.

 

기본적으로 네트워크 플로우는 이전 단계에서의 해로부터 다음 단계의 해를 구할 때 이전 단계에서의 일부 과정을 필요에 따라 수정하거나 취소할 수 있다는 것이 장점이며, 위에서 봤듯이 "경로의 방향을 거꾸로 바꾼다" 라는 개념이 그것을 가능하게 해 준다.

 

----------------------------------------------------------------------------------------------------------------

이제 그 유명한 min-cut max-flow theory에 대해 알아보자.

아래 방향그래프에 대해, 다음 두 문제를 생각해보자.

1. 방향간선의 가중치는 그 간선을 따라 흐를 수 있는 물의 최대량을 나타낸다고 할 때, S점에서 E점까지 흐를 수 있는 물의 최대 양은 얼마나 될까?

2. S점에서 E점까지의 경로가 없도록 하기 위해 방향간선을 몇 개 없애려고 한다. 방향간선의 가중치는 그 간선을 없애기 위한 비용을 나타낸다고 할 때, S점에서 E점까지의 경로가 존재하지 않도록 간선을 제거하는 최소 비용은 얼마일까?

 

1번 문제는 maximum flow 문제이고 2번 문제는 minimum cut 문제이다. 그리고 놀랍게도 위의 1, 2번 문제는 동치이다!
이에 관련한 이론들은 구글링해보면 많이 나올 것이고 여기서는 그냥 풀이법만 간단히 설명하겠다.

1번 문제 - 즉 maximum flow 문제 기준으로 설명하겠다.

아까처럼 답을 저장하는 변수를 s라고 하고 초기값을 0으로 두자.

시작점부터 끝점까지 이어지는 어떤 경로를 찾았다고 하자. 이 경로를 따라 흐를 수 있는 물의 최대 양은 그 경로상의 방향간선들의 가중치의 최소값이다. 그 최소값을 x라고 하자(아래 예에서는 x=4이다).

그러면 s에 x만큼의 값을 더해주고, 그 경로의 가중치들에서는 x만큼의 값을 각각 다 뺀다. 또한 도착점부터 시작점까지 거꾸로 진행하는 간선들을 새로 생성하고, 가중치를 전부 x로 둔다.

그림에서는 가중치가 0이 된 간선은 그리지 않았다.

이 과정을 시작점부터 끝점까지 물이 흐를수 있는 경로가 없을 때 까지 진행한다(시작점부터 끝점까지의 경로가 존재해도 그 경로상에 가중치가 0인 간선이 있다면 물이 흐를 수 있는 경로가 아니다).

위 과정이 끝난 시점에서의 s값이 답이 된다. 물론 여기서도 역추적을 통해 물이 어떻게 흘러가야 하는지 구해낼 수 있다.

그림 그리기가 귀찮은건 아닌데.. 여기까지 따라오신 분들은 충분히 다음 과정들을 스스로 하실 수 있기 때문에 위 문제에 대해 더이상 그림은 넣지 않겠다. 절대 내가 그리기 싫어서 안 그린게 아니다.

 

풀이법을 이해하더라도 이게 왜 답이 될까라는 의문이 남을 수 있는데, 스스로 예제 입력을 몇개 만들어서 손으로 그리면서 풀다보면 직관적으로 납득이 갈 것이다. 그래도 찝찝하다면 구글링을 해보시길... 난 정말 무책임한 놈임ㅠ

그리고 이쯤되면 눈치챈 분들도 있겠지만 맨 처음 소개한 문제는 그래프의 간선의 가중치를 다 1로 둔 min-cut max-flow 문제라고 할 수 있다.

 

이제 min-cut max-flow 방식으로 풀 수 있는 문제들을 몇개 더 소개한다.

----------------------------------------------------------------------------------------------------------------

PKU 1149 PIGS - http://poj.org/problem?id=1149, http://211.228.163.31/30stair/pigs/pigs.php?pname=pigs
PKU 3614 Sunscreen - http://poj.org/problem?id=3614

전형적인 max-flow 문제들. 만약 간선의 가중치를 무한대로 잡아야 할 필요가 있을 때는 그냥 충분히 큰 값으로 설정해주면 된다.

----------------------------------------------------------------------------------------------------------------

PKU 3041 Asteroids - http://poj.org/problem?id=3041 , http://211.228.163.31/pool/asteroid/asteroid.php?pname=asteroid

이 문제는 난해해 보이나, 문제에 담긴 생각해내기 힘든 어떤 동치 관계를 생각해 낼 수만 있다면 쉽게 풀 수 있다.

----------------------------------------------------------------------------------------------------------------

다음 포스팅에는 Bellman-Ford 알고리즘을 같이 써서 풀 수 있는 네트워크 플로우 문제들을 소개하겠다.

 

Re-Harmonization 연습삼아 만들어봣음
워낙 유명한 곡이라 리믹스버전도 많긴한데 이런 류의 리믹스는 없는듯해서..
여기다 좀 섬세한? 남자보컬을 넣고싶다 멜로디라인 다짜놧는데 으 전역하면 마이크사서 녹음해야지 ㅎㅎ 

인덱스드 트리에서는 원소 하나를 갱신할 때마다 logN의 시간이 든다. 그런데 여러개의 연속적인 원소를 한꺼번에 갱신할 때는 (원소의 개수) * logN 의 시간이 들게 되므로 비효율적이다.

Lazy Propagation이란, 연속한 구간을 한꺼번에 갱신해야할 경우에 사용되는 방법으로, 매번 일일히 갱신을 하지 않고 필요할 때만 갱신을 해주는 방법이다. 말 그대로 해석하면 '게으른 전파' 방식이다. 가장 기본적인 문제를 통해 알아보자.

-------------------------------------------------------------------------------------------------------------

PKU 3468 - A Simple Problem With Integers
http://poj.org/problem?id=3468

N개의 숫자가 입력으로 들어온다. 다음에는 Q개의 쿼리문이 들어오는데, "Q a b" 형태의 쿼리문은 a번째숫자부터 b번째숫자까지의 총합을 구하는 것이고, "C a b c"  형태의 쿼리문은 a번째부터 b번째까지의 모든 숫자들에 c값을 더하라는 의미이다.
N, Q는 최대 십만이며, 각각의 숫자는 마이너스 십억에서 십억 사이의 범위 내에 있으나 숫자들의 합은 32-bit integer 범위를 넘어설 수 있다.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15



이 문제를 단순한 인덱스드 트리로 풀면 "C a b c" 형태의 쿼리문을 수행하는 데에는 (b-a+1) * logN의 시간이 들며 이 형태의 쿼리문만 십만개가 들어올 경우 Time Limit Exceeded가 뜨게 된다. 이것을 해결하기 위해 Lazy Propagation을 써보자.

설명을 위해, N=32일 경우를 들겠다. 저거 그리느라 눈알 아파 죽는줄 알았다.

이제 여기서 "C 5 23 10" 이런 쿼리문이 들어왔다고 해보자. 5번째부터 23번째 숫자까지 10을 더하라는 의미이다. 일단 5번째 숫자부터 23번째 숫자에 해당하는 구간을 트리에 나타내보면 아래와 같다.

그러면, 저렇게 빨간색으로 표시된 노드와 그 노드들의 상위 노드들만 일단 업데이트 시켜준다.
아래 그림으로 좀더 자세히 설명하면, 트리의 노드에 값을 두 종류를 만들어놔서 하나는 인덱스드 트리의 대표값, 나머지 하나는 이 노드의 하위 노드들을 업데이트 시켜야 된다는 일종의 알림 값으로 하고, 빨간색으로 표시된 노드의 알림 값은 10으로 할당해주고 그 상위의 하늘색 노드들의 대표값에 (자기 자식들의 수) * 10 만큼의 값을 더해주는 것이다.
바로 이해가 안가면 그냥 하늘색 노드는 이미 갱신된 노드고 빨간색 노드는 자기 자식 노드들이 아직 갱신이 안된 노드라고 생각하고 계속 읽어주기를 바란다.

이제 이 상태에서, "Q 10 18" 이런 쿼리문이 들어온다면 어떨까?

일단 10번째부터 18번째 까지의 숫자 범위를 아래 그림에서 보라색으로 표시하면 다음과 같다.
근데 이 상태에서 보라색 노드들의 대표값들을 다 더한 것이 답이 될수는 없다. 왜냐하면 아직 보라색 노드에는 이전 쿼리문이 갱신되지 않았기 때문이다. 따라서 아래 그림과 같이 빨간색 노드들을 보라색 위치까지 끌어내려서 갱신하면 된다.

코딩하려는 사람들을 위해 좀더 자세히 설명하면, 각각의 보라색 노드들에서 루트 노드까지 올라가면서 빨간색 노드가 있는지를 체크한다. 만약 있다면, 빨간색 노드로부터 쭉 아래로 타고 내려오면서 갱신해 주면 된다.


갱신이 끝나면, 값을 다 더해서 출력해 주면 된다.

시간이 얼마나 걸리는 지를 보자. 일단 "C a b c" 이 쿼리문으로 인해 생기는 빨간색 노드의 개수는 약 log(b-a+1)개이고, 그 노드로부터 루트까지 갱신해줘야 하므로(하늘색 노드) 최대 log(b-a+1) * logN의 시간이 든다. 트리의 높이가 logN이기 때문이다.
여기서 b-a+1 의 값이 최대 N이므로 logN * logN = (logN)^2 의 시간이 들게 된다.

"Q a b" 쿼리문을 실행할 때도 마찬가지로 해당 구간의 숫자합을 구하기 위해 더해줘야할 대표값 노드는 log(b-a+1)개이고
각각의 노드를 루트에서부터 갱신해줘야되므로 노드 하나당 logN만큼의 처리 시간이 필요하므로 같은 계산 과정에 의해 (logN)^2 의 시간이 들게 된다.

결국 전체 실행시간은 Q * (logN)^2 가 되고,
Q * (logN)^2 <= 100,000 * (log100,000)^2 < 100,000 * 17^2 = 28,900,000 < 100,000,000 가 되므로 1초 내에 해결 가능하다.

추가로 고려해야 할 것은 숫자들의 합이 int범위를 넘어갈 수 있으므로 그냥 __int64 형태로 변수들을 선언하면 된다.

보면 어려워 보이지만 한번 코딩으로 익혀놓으면 의외로 쉽다. 나도 그냥 구글에서 아이디어만 얻고 혼자 터득했으니..





자, 그런데 한가지 주의해야할 점이 있다. 갱신할때 "갱신 순서"가 바뀌면 안되는 경우가 있다.
무슨 말이냐면, 위 문제처럼 값을 더하는 경우는 어떤 노드에 3을 더하고 5를 더하는 경우랑 5를 더하고 3을 더하는 경우랑 똑같은 결과가 나온다. 하지만 그런 교환법칙이 성립하지 않는 문제의 경우 Lazy Propagation을 사용할 때에 각별한 주의를 요한다. 
다음 문제를 보자.

-------------------------------------------------------------------------------------------------------------

PKU 2777 - Count Color
http://poj.org/problem?id=2777

칠판에 L개의 칸이 있고, T가지의 색깔이 있다. 이제 다음 O개의 쿼리문이 입력으로 들어온다.
"C a b c" 형태의 쿼리는 a번째 칸부터 b번째 칸까지 c번째 색깔로 칠하라는 의미이다. 이미 다른 색깔이 칠해져 있다고 해도 그 위에 덮어서 칠한다. 색이 섞여서 변해버리는 경우는 없다.
"P a b" 형태의 쿼리는 a번째 칸부터 b번째 칸까지의 연속된 칸들에 칠해진 색깔의 종류가 몇개인가를 출력하라는 의미이다.

L, O는 최대 십만이며, T는 최대 30이다. 또한, 입력된 쿼리문에서 a가 b보다 더 클 수도 있다.

Sample Input

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

Sample Output

2
1

일단 이 문제에 인덱스드 트리를 어떻게 적용해야 할까 생각해보자. 색깔이 30개이므로 인덱스드 트리를 30개를 만들어서 하는 것은 미친 짓이다. 코딩할때도 정신건강에 안좋을 뿐더러, 아까 계산한 결과 O * (logL)^2 의 값이 28,900,000 정도 되는데 여기 30을 곱하면 시간 초과가 되기 때문이다.

머리를 잘 굴려야 된다. 자랑은 아니지만 필자는 T가 30인걸 보고 바로 떠올렸다.
int 범위가 양수는 2^31 까지이므로, 이진수를 생각해서 이진수의 k번째 자리가 1이면 k번째 색깔이 포함되어 있다는 의미로 대표값을 정의한다. 그러면 인덱스드 트리에서 구간의 대표값들을 다 OR 연산을 해 준다음 이진수의 각 자릿수의 합을 구하면 그것이 색깔의 종류의 개수가 된다!!
OR연산은 매우 빠르게 이루어지므로 이렇게 하면 O * (logL)^2 시간만에 해결할 수 있다.



이제 아까 언급한 "갱신 순서"에 대해 이야기할 차례가 왔다. 어떤 칸에 1번 색을 먼저 칠하고 2번 색을 칠한 경우와, 2번 색을 먼저 칠하고 1번 색을 칠한 경우는 결과가 다르다. 이 문제는 어떤 것이 먼저 갱신된 것인가를 잘 고려해줘야 하는 문제인 것이다.


크게 두 가지 해결 방법이 있다.

첫번째는 Time Stamp를 설정해주는 것이다. Time Stamp는 데이터가 어떤 시점에 존재했는가를 표시해주는 것인데, 따라서 갱신을 할 때 이것은 몇번째 쿼리문에 의해 갱신된 것이다 이렇게 표시를 해주면, "P a b" 쿼리문을 수행할 시 루트부터 내려오면서 갱신해 줄 때에 빨간색 노드를 여러 개 만났을 때, 나중에 들어온 쿼리문에 우선순위를 두어서 갱신해주면 된다.

두번째는 "C a b c" 쿼리문의 수행 과정에서 빨간색 노드들을 선택할 때, 각각의 선택된 노드에서 루트까지 거슬러 올라가면서 이전 쿼리문에 의해 생긴 빨간색 노드가 있나 본 다음 있으면 "P a b"쿼리문을 수행할 때와 같이 다시 내려오면서 갱신해 준다음에 해당 쿼리문을 적용하는 것이다.
매번 이렇게 해주면 "루트부터 해당 노드까지의 노드들 사이에 빨간색 노드들이 2개 이상 있을 시 루트에 가까운 쪽이 제일 나중에 입력된 쿼리이다" 라는 사실이 보장된다!! 왜냐하면 매번 자기 위의 빨간 노드들을 없애고 갱신하기 때문에 어떤 "C a b c"쿼리가 입력된 시점에서는 그 쿼리에 의한 빨간색 노드들의 위에는 이전 쿼리로 인한 빨간색 노드가 없기 때문이다. 따라서 "P a b" 쿼리를 수행할 때 각각의 선택된 노드로부터 루트까지 쫙 훑으면서 다른 빨간색 노드들을 무시하고 루트에 제일 가까운 빨간색 노드만을 아래로 내려가면서 쭉 갱신해주면 된다.

개인적으로는 두번째방법을 강추한다. 이것저것 생각하느라 머리아플일이 크게 없기 때문이다.


필자가 설명 솜씨가 부족해서 한번 읽으면 잘 이해가 안 갈 수도 있으니 스스로 생각하면서 깨닫길 바란다.


-------------------------------------------------------------------------------------------------------------


요약하자면, Lazy Propagation은 연속된 구간을 한꺼번에 갱신할 때에 사용되는 방법으로, 쿼리문이 M개이고 원소의 개수가 N개이면 M*(logN)^2 의 시간복잡도를 가진다. 그런데 갱신 순서가 바뀌면 안되는 경우에는 그에 대한 처리를 따로 해주어야 한다.