※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.
들어가기 전에
저번 공부기록에 이어서 이번에도 Semi-Game Cup 4 오프라인 대회에 나갔던 이야기로 글을 시작한다.
글쓴이는 대회중에 A부터 E까지 해결한 다음 이어서 F번 문제를 읽었다. 그리고 문제에 등장한 수식 \(\frac{\sum S_i}{\sum D_i}\)을 보자마자 가져갔던 레퍼런스 문서에 적어둔 Dinkelbach's Algorithm의 형태가 떠올랐고, 이를 활용하면 문제를 해결할 수 있지 않을까 하는 생각이 들었다.
그러나 글쓴이는 Dinkelbach's Algorithm은 물론 이러한 분수 형태의 값을 최적화하는 유형의 문제를 한 번도 풀어 본 적이 없었고, 문서에 적어간 내용을 활용할 충분한 배경지식이 있지도 않았다. 단순한 활용 문제가 나왔을 때 사용하면 좋겠다는 정도로만 생각하고 레퍼런스 문서 채우기용으로 대충 넣기만 했었기 때문이다. 그렇게 글쓴이는 문제 해결에 유효한 접근은 하지 못한 채로 대회를 마쳤다.
글쓴이는 다음에 이와 같은 유형의 문제를 만나면 당황하지 않게끔, 다음으로 공부할 주제를 이러한 유형으로 결정하였다.
개요
PS/CP 문제를 해결하다 보면 \(\frac{\sum A_i}{\sum B_i}\)의 꼴로 나타나는 값의 최적화를 요구하는 문제를 종종 만나볼 수 있다. 이런 형태의 문제는 어떻게 해결할 수 있을까?
이 글에서 위와 같은 문제를 해결하는 두 가지 방법을 설명한다.
0-1 Fractional Programming
0-1 Fractional Programming(0-1 분수 계획법)은 두 길이 \(n\)인 수열 \(a_i\)와 \(b_i\)가 주어졌을 때, feasible set \(\displaystyle \Omega\subseteq\{0,1\}^n\)의 원소 \(x=(x_1,x_2,\cdots,x_n)\)에 대한 \(\frac{\sum_{i=1}^n a_i x_i}{\sum_{i=1}^n b_i x_i}\)의 값의 최댓값 또는 최솟값을 구하는 문제를 말한다. \(\{0,1\}^n\)은 유한집합이므로, 주어진 값의 최댓값 또는 최솟값은 항상 존재함을 확인하자. 이 글에서는 최댓값을 구하는 방법을 위주로 설명할 것이다. 최솟값을 구하는 방법도 뒤의 설명과 크게 다르지는 않다.
일반적으로 \(\{0,1\}^n\) 꼴의 원소에서 0은 해당 인덱스를 선택하지 않음을 의미하고, 1은 해당 인덱스를 선택함을 의미한다.
이 글에서는 각 \(x\in\Omega\)에 대하여 \(\sum_{i=1}^n b_i x_i>0\)을 가정한다. 이 조건은 \(n\)개의 수를 모두 0을 골라 분모를 0으로 만드는 것을 막는다. 대부분의 문제 상황에서 위의 식으로 표현되는 값은 평균, 가중평균, 비율(가치/비용, 가치/무게 등)등이므로 이러한 가정을 하여도 문제될 일이 거의 없다.
문제 이해를 돕기 위해, 0-1 Fractional Programming으로 변환할 수 있는 간단한 두 문제를 소개한다. 이 두 문제는 0-1 Fractional Programming을 몰라도 해결할 수 있다.
\(\Omega\)를 크기가 1 이상인 모든 연속부분배열에 대응시키면 0-1 Fractional Programming 문제가 된다.
\(\Omega\)를 크기가 2 이상인 모든 연속부분배열에 대응시키면 0-1 Fractional Programming 문제가 된다.
Solution of 0-1 Fractional Programming
이 문제의 잘 알려진 해법은 식을 적절하게 변형하여 이분 탐색을 활용한 parametric search를 이용하는 것이다.
\(x\in\Omega\)에 대하여 \(\frac{\sum_{i=1}^n a_i x_i}{\sum_{i=1}^n b_i x_i}\)의 최댓값을 \(\lambda^*\)라 하고, 이 값을 갖게 하는 \(x\)(중 하나)를 \(x^*\)라 하자.
그렇다면 정의에 따라 \(\frac{\sum_{i=1}^n a_i x_i}{\sum_{i=1}^n b_i x_i}\le\lambda^*\)가 성립하며, 등호를 만족시키는 \(x\)가 존재한다.
이 때, \(x\in\Omega\)에 대하여 \(\sum_{i=1}^n a_i x_i - \lambda^*\cdot\sum_{i=1}^n b_ix_i \le 0\)도 항상 성립하게 됨을 관찰하자. 이에 대한 보충설명을 하면, 등호조건은 \(x=x^*\)일 때 만족하고, 좌변의 식의 값이 0보다 크게 하는 \(x\)가 존재한다면 그 때의 \(\frac{\sum_{i=1}^n a_i x_i}{\sum_{i=1}^n b_i x_i}\) 값이 \(\lambda^*\)보다 커져 모순이 발생한다는 점을 잘 생각해보자.
\(\sum_{i=1}^n b_i x_i\)이 양수이므로, \(\sum_{i=1}^n a_i x_i - \lambda\cdot\sum_{i=1}^n b_ix_i\)는 \(\lambda<\lambda^*\)이면 최댓값이 음수, \(\lambda=\lambda^*\)이면 최댓값이 0, \(\lambda>\lambda^*\)이면 최댓값이 양수가 됨을 확인하자. 따라서, \(\lambda\)값을 하나 정했을 때 \(\sum_{i=1}^n a_i x_i - \lambda\cdot\sum_{i=1}^n b_ix_i\)의 최댓값을 계산할 수 있다면 \(\lambda^*\)가 존재하게 될 초기구간을 먼저 정한 다음 그 범위에서 이분 탐색을 활용한 parametric search를 하는 것으로 \(\lambda\)의 값을 계산해낼 수 있다.
이 과정에서, 일반적으로 식 \(\sum_{i=1}^n a_i x_i - \lambda\cdot\sum_{i=1}^n b_ix_i\)은 \(\sum_{i=1}^n x_i(a_i - \lambda\cdot b_i)\)와 같이 정리하여 사용한다.
Dinkelbach's Algorithm
위의 방법만으로도 이 유형의 문제 상당수를 해결할 수 있다. 그러나 이 방법만으로는 몇몇 문제에서 어려움을 겪을 수도 있다. \(\lambda^*\)의 값은 유리수로 나올 수도 있으므로 여러 중간 과정에서 부동소수점 오차를 신경써줘야 하기 때문이다. 0-1 Fractional Programming의 문제 해결과정에서 이러한 부동소수점 연산을 없애버릴 수는 없을까?
Dinkelbach's Algorithm은 0-1 Fractional Programming의 최적해 \(x\in\Omega\)를 추가적인 부동소수점 연산 없이 찾는 한 가지 해결 방법이다. 이 알고리즘을 활용하면 \(\lambda^*\)의 값을 부동소수점 연산 없이 유리수의 형태로 구할 수 있다. 앞서 소개한 방법은 부동소수점을 활용하고 충분한 정확도를 확보하기 위해 많은 루프를 돌아야 하므로 일반적으로 Dinkelbach's Algorithm을 활용한 방법보다는 느리다.
다음은 Dinkelbach's Algorithm의 과정이다.
(1) 먼저 적당한 초기값 \(\lambda\)를 정한다. 조건을 만족하면서 계산하기 편한 \(x\in\Omega\)중 하나를 골라 \(\frac{\sum_{i=1}^n a_i x_i}{\sum_{i=1}^n b_i x_i}\)의 값을 하나 계산하면 된다.
(2) \(\sum_{i=1}^n x_i(a_i - \lambda\cdot b_i)\)가 최댓값을 갖게 하는 \(x\)를 구한다.
(3) 이 \(x\)에 대하여 \(\sum_{i=1}^n x_i(a_i - \lambda\cdot b_i)\) 의 값이 0이 아니라면 \(x\)에 대한 \(\frac{\sum_{i=1}^n a_i x_i}{\sum_{i=1}^n b_i x_i}\) 의 값을 새로운 \(\lambda\)값으로 하여 (2)로 돌아간다. 0이라면 \(x\)에 대한 \(\frac{\sum_{i=1}^n a_i x_i}{\sum_{i=1}^n b_i x_i}\) 의 값을 최적해로 결정하고 알고리즘을 종료한다.
앞서 소개한 이분 탐색을 활용한 parametric search와 풀이 방법은 비슷하지만, Dinkelbach's Algorithm은 답을 찾아가는 과정에서 이분 탐색을 사용하지 않고 계산한 결과를 다시 활용한다. 이러한 과정은 수치해석에서의 Newton-Raphson Method의 과정과 유사하다고 볼 수 있다.
0-1 Fractional Programming에서의 Dinkelbach's Algorithm은 최악의 경우 \(O(\lg n+\lg A + \lg B)\)회 루프를 돌면 종료된다는 것을 증명할 수 있다. 여기에서 \(A\)는 \(a_i\)의 최댓값, \(B\)는 \(b_i\)의 최댓값을 의미한다. 위의 루프 횟수를 보면 증명 방법이 감이 올테니 구체적인 증명은 생략한다.
여담
Dinkelbach's algorithm보다는 이분 탐색을 사용한 parametric search의 구현이 더 쉽고 웬만한 문제는 다 해결할 수 있으니 Dinkelbach's algorithm은 이해를 못 하더라도 이분 탐색을 사용한 parametric search 풀이만큼은 이해하고 넘어가는 것을 추천한다.
0-1 Fractional Programming 문제의 최선의 해결 방법이 항상 이분 탐색을 활용한 parametric search나 Dinkelbach's Algorithm인 것은 아니다. 예를 들어, 방향그래프에서 minimum mean weight cycle을 탐색하는 문제는 Karp's Algorithm(Karp's Minimum Mean Cycle Algorithm)을 이용해 본문의 방법보다 더 빠르게 해결할 수 있다.
관련 문제
[BOJ7686] Dropping Tests, [BOJ27654] 시험
0-1 Fractional Programming 기본 문제이다.
위의 문제와 같지만, 추가적으로 해를 구성하는 보석의 집합을 구해야 한다.
길이가 \(K\) 이상인 연속부분배열에 대한 0-1 Fractional Programming 문제로 볼 수 있다.
Kadane's Algorithm과 0-1 Fractional Programming을 같이 활용해보자.
[BOJ8925] GC-비율
위의 문제와 유사하지만, 추가적으로 그 평균의 최댓값을 가지는 구간을 구해야한다.
부동소수점 자료형을 활용하면 구간을 선택하는 tie-breaking 조건들을 확인할 때 문제가 일어나기 매우 쉽다.
유리수의 형태로 \(\lambda\)의 값을 표현하고, 이진탐색이 아닌 Dinkelbach Algorithm을 이용하면 부동소수점 오차 걱정 없이 정수 자료형만으로 문제를 해결할 수 있다.
[BOJ10019] Sabotage
(양 끝이 포함되지 않은) 연속부분배열을 제거한 배열에 대한 0-1 Fractional Programming 문제로 볼 수 있다.
무게의 합이 \(W\) 이상인 부분집합에 대한 0-1 Fractional Programming 문제로 볼 수 있다.
knapsack DP와 0-1 Fractional Programming을 같이 활용해보자.
글쓴이가 0-1 Fractional Programming을 공부하게 된 계기가 된 문제이다.
문제를 해결한 지금 시점에서 돌아보면, 문제 자체를 잘못 이해했어서 이 개념을 제대로 이해했더라도 대회 시간중에 문제를 해결하지 못했을 것이다...
추가점수는 1점 미만이지만 정한 구간에서 처리하지 못한 노트가 있다면 2점 이상의 감점이 발생하므로, 구간을 정한다면 해당 구간의 모든 노트를 처리해야 한다. 이 관찰을 이용하여 문제를 해결해보자.
[BOJ17986] Great GDP
1번 정점을 포함하는 subtree에 대한 0-1 Fractional Programming 문제로 볼 수 있다.
tree dp와 0-1 Fractional Programming을 같이 활용해보자.
[BOJ6141] Sightseeing Cows
시작점을 자유롭게 고를 수 있고, 둘 이상의 사이클로 분해 가능한 사이클의 경우 그 분해된 사이클 중 적어도 하나는 원래의 사이클 이상의 평균 즐거움을 줄 수 있다는 점을 관찰하자. 이를 이용하면 이 문제는 (둘 이상으로 분해할 수 없는) 모든 부분사이클에 대한 0-1 Fractional Programming 문제로 볼 수 있다.
negative cycle detection과 0-1 Fractional Programming을 같이 활용해보자.
위 문제와 같은 형태로 모델링할 수 있는 다른 문제이다.
\(G\)의 부분그래프에 대하여 \(\frac{\lvert E\rvert}{\lvert V\rvert}\) 의 최댓값을 구하는 것은 \(\lvert E\rvert - \lambda\lvert V\rvert\)의 최댓값이 0이 되게 하는 \(\lambda\)의 값을 찾는 것과 같다.
고정된 \(\lambda\)에 대하여 위 식을 최대화하는 그래프를 찾는 것은 각 간선을 고르면 점수를 1씩 얻고 정점을 고르면 점수를 \(\lambda\)씩 잃으며 각 간선을 골랐을 때 그 간선을 구성하는 양 끝의 두 정점은 항상 골라야하는 관계가 있을 때 정점과 간선을 적절히 골라 얻을 수 있는 점수를 최대화하는 그래프를 찾는 것과 같다. 이 문제는 주어진 그래프의 간선과 정점을 각각 새로운 정점으로 하고 간선과 정점의 관계를 새로운 간선으로 하는 Project Selection Problem으로 모델링할 수 있다. (참고: 공부기록06)
주어지는 그래프에 간선이 없을 수도 있다는 점에 유의하자.
참고 자료
https://www.keisu.t.u-tokyo.ac.jp/data/1992/METR92-14.pdf
https://codeforces.com/blog/entry/146040
'CP자료모음' 카테고리의 다른 글
| [PS/CP 공부기록] 06. Maximum Closure Problem, Project Selection Problem, Maximum Weight Independent Set, 燃やす埋める問題 (0) | 2026.02.07 |
|---|---|
| [PS/CP 공부기록] 04. Green Hackenbush (0) | 2026.01.28 |
| [PS/CP 공부기록] 03. Cartesian Tree, Treap, Implicit Treap (0) | 2026.01.13 |
| [PS/CP 공부기록] 02. System of Difference Constraints (0) | 2026.01.07 |
| [PS/CP 공부기록] 01. Minimum Steiner Tree in Graph (0) | 2026.01.02 |