2024년 1-2월 알고리즘 문제풀이

이런 류 문제는 대부분 그래프를 적절히 변형하여 모델링한 다익스트라 가 됩니다. 비슷하게 풀 수 있습니다.

먼저, 1번에서 $n$번으로 가는 최단 경로 $P$가 있다면, 가는 경로를 $P$로 고정해도 상관없음을 관찰합니다. 만약 가는 경로와 오는 경로가 모두 $P$와 다르다면, 그중 하나를 $P$로 바꾸어도 손해가 발생하지 않습니다. 가는 경로와 오는 경로를 맞바꾸어도 상관없으므로, $P$로 $n$에 도달했다고 생각해도 상관 없습니다.

이제, $P$와 다르면서 최단인 경로를 찾아야 합니다. 정점 $v$들마다 새로운 정점 $v’$를 생각하고, 간선 $(u, v, t)$에 대해 (실제로는 양방향입니다)

• 항상 $(u, v, t)$와 $(u’, v’, t)$를 추가하고
• 만약 $(u, v)$ 간선이 $P$에서 사용되지 않았다면, $(u, v’, t)$와 $(u’, v, t)$를 추가한

그래프를 생각합니다. 이는 그래프를 위와 아래 두 층으로 나누어서, 위-그래프와 아래-그래프 각각이 $G$와 똑같이 생겼으면서, $P$에 포함되지 않은 간선들만 이용하여 아래-그래프로부터 위-그래프로 이동할 수 있도록 한 셈이 됩니다.

이제, 아래-그래프의 $n$번에서 출발하여 위-그래프의 $1$번인 $1’$ 으로 이동하는 최단 경로를 찾으면 됩니다.

비슷한 문제는 정말 흔한것 같습니다. 경로의 홀짝성, 특정 점을 밟았는지 여부 등 다양한 최단 경로 문제에 이용됩니다.

중복된 수가 없는 행 또는 열을 슬프다 고 하겠습니다. (Sad? ㅋㅋㅋㅋㅋㅋ 문제풀때 실제로 이런식으로 말했던거 같은데, 공식 해설은 Colorful 같은 행복한 용어를 사용합니다.)

$r$번째 행과 $c$ 번째 열이 모두 슬픈 경우, $(r, c)$ 칸의 원소를 아무것으로나 바꾸어줌으로써 양쪽의 슬픔을 동시에 해소할 수 있습니다. (가능한 수가 $1$부터 $n$까지밖에 없기 때문에, 어떤 행/열이 슬프다면 항상 1부터 $n$까지의 수가 정확히 한 번씩 사용되고 있기 때문입니다)

$r$번째 행이 슬프지만 $c$번째 열이 슬프지 않은 경우, $(r, c)$ 칸의 원소를 적절히 바꾸어야 합니다.

적절히 바꾸는 것만 조심한다면, 행렬 전체의 슬픔은 매번 2 또는 1만큼씩 줄어듭니다. Priority Queue 등의 적절한 자료구조를 이용하여 2만큼 줄일 수 있을때 항상 그리한다면 최소 횟수만에 해결할 수 있습니다.

공식 해설에는 최적성에 대한 더 깔끔한 증명이 있습니다. 일반성을 잃지 않고 슬픈 열의 개수 $m_c$가 슬픈 행의 개수 $m_r$보다 적다고 하면, 항상 열의 슬픔을 교정하는 식으로 접근합니다. 그러나 이때 첫 $m_r$번은 행과 열을 동시에 교정할 수 있습니다. 이렇게 하면 $min(m_r, m_c)$ 번이 됩니다.

팀장을 배치하는 것과 팀의 수를 선택하는 두가지 작업을 할 수 있다는 점이 어렵습니다.

먼저, $k$가 고정되어 있다고 치고 팀장의 위치만 움직여 가며 문제를 푼다고 생각해 봅니다. 배치가 결정되면 $O(n)$ 시간에 각 팀의 실력을 계산할 수 있지만, 계산해야 할 자리가 $n$개이기 때문에 이 방법으로는 복잡도를 맞출 수 없습니다. 그러나, 다음 관찰로 복잡도를 줄일 수 있습니다.

관찰: 팀장을 오른쪽으로 한 칸 옮길 때, 소속된 팀이 바뀌는 사람은 팀장과 방금 자리를 바꾼 사람 두명밖에 없다.

팀 $k$개의 실력을 적절한 자료구조를 이용하여 유지한다면, 최대 두 팀만 실제로 실력값이 바뀌게 되고, 그 과정에서 최대와 최소를 유지해야 하므로 $O(\log k)$ 시간에 팀장을 한 칸 옮겨볼 수 있습니다. $k \leq n$ 이므로, 이는 즉 팀장을 맨 왼쪽부터 맨 오른쪽까지 옮기면서 최적배치를 계산하는 데 $O(n \log n)$ 시간을 쓴다는 것입니다.

이제, $n$의 각 약수 $k$에 대해 따로 문제를 푼다고 생각하고, 전체 복잡도를 계산해 봅시다. $n$의 약수의 개수를 $d(n)$ 이라고 쓸 때, \(\sum_{k \di n} n \log k = O(d(n) \times n \log n)\) 입니다. ($\log k$를 타이트하게 잡아도, $\sum_{k \di n} \log k$ 는 $(d(n) \log n) / 2$ 이므로 변하지 않습니다) $d(n)$은 꽤 작은 값이지만, $n = 10^6$ 이하에서 $d(n)$의 최댓값은 무려 240임을 (720,720이 240개의 약수를 가집니다) 생각하면 시간상 무리해 보입니다.

따라서, 다음의 관찰을 통해 복잡도를 더 줄여야 합니다.

관찰: 팀의 개수는 반드시 $n$의 소인수일 때 최적이다.

이는 임의의 정수 $m > 1$에 대해, $k$팀을 만드는 것보다 $mk$팀을 만드는건 항상 손해임을 보이면 됩니다. 증명은 비교적 간단한데, formal하게 작성하기보다는 2팀을 만들지 4팀을 만들지의 예시를 들어 생각해보겠습니다. 4팀 상태에서 팀 4개를 강한 순서대로 나열하면, 2팀으로 팀을 줄일때 1번과 3번, 2번과 4번 팀이 묶이게 됩니다. 이때 강한쪽 팀은 1번팀의 2배보다 약하고, 약한쪽 팀은 4번팀의 2배보다 강해지기 때문에 강한 팀과 약한 팀의 실력 비율은 더 공정해집니다.

따라서, $n$의 모든 약수가 아닌 소인수들에 대해서만 풀면 되고, 100만 이하의 수는 최대 소인수가 7개뿐이므로 $n \log n$의 상수배 (7) 만에 해결할 수 있습니다.

사실 PS에 이런 문제를 낸 저의까지는 잘 모르겠습니다만, TCS / DB / DM 모두에서 유명하고 실제 research도 많이 된 문제입니다. Wikipedia에 이 문제에 대한 글도 있습니다.

아마도 출제 의도는 Goldberg나 Tarjan의 flow 기반한 알고리즘이었던 것으로 보입니다. 이 문제는 적절하게 min-cut 문제로 모델링할 수 있고, 이를 flow로 해결할 수 있으므로…

다만 저는 이 문제를 PS하다가 본게 아니라, 연구실에서 관련 논문을 통해 접했습니다. 최근 제시된 구현하기 비교적 어렵지 않은 approximation 알고리즘 [1]이 있어서 구현해보고 제출했습니다. 기본적인 아이디어는 Core Decomposition (나중에 언젠가 소개할 기회가 있을 것 같습니다) 을 수행하면 dense한 영역을 대강 찾아준다는 것에 착안하여 이를 반복하는 것인데, 나중에 이론적으로도 정확한 approximation ratio에 대한 증명이 이루어졌습니다 [2].

이외에도 이 문제를 비롯하여 관련한 여러 문제에 대한 연구가 활발히 이루어지고 있습니다. 여전히 PS 대회에서 flow 알고리즘이 생각해낼만 한지는 잘 모르겠습니다.

1. Digvijay Boob et al. Flowless: Extracting Densest Subgraphs Without Flow Computations, (2020)

2. Kent Quanrud Chandra Chekuri, and Manuel R. Torres, Densest Subgraph: Supermodularity, Iterative Peeling, and Flow, (2022)