리스트 분할 최대 스코어 달성: 동적 계획법과 Li Chao Tree 활용 전략

핵심 기술

본 콘텐츠는 정수 리스트를 k개의 연속된 부분으로 분할하여 각 부분의 합을 제곱한 값의 총합을 최대화하는 문제를 다룹니다. 이를 위해 접두사 합(Prefix Sums)을 이용한 빠른 구간 합 계산과 동적 계획법(DP)을 기본으로 하되, DP의 시간 복잡도를 개선하기 위해 Li Chao Tree를 활용하는 고급 최적화 기법을 소개합니다.

기술적 세부사항

• 문제 정의: $n$개의 정수 리스트를 $k$개의 비어 있지 않은 연속된 부분으로 분할하여, 각 부분의 합을 제곱한 값의 합이 최대가 되는 경우를 찾습니다.
• 접두사 합 활용: 리스트의 모든 구간 합을 상수 시간에 계산하기 위해 접두사 합 배열을 사용합니다. $P[i]$는 arr[0]부터 arr[i-1]까지의 합을 나타냅니다.
• 동적 계획법 (DP): $dp[j][i]$를 첫 $i$개의 원소를 $j$개의 부분으로 분할했을 때의 최대 스코어로 정의합니다. $dp[j][i] = max_{0 le t < i} (dp[j-1][t] + ( ext{sum}(t+1, i))^2)$ 의 점화식을 가집니다.
• 시간 복잡도: 단순 DP는 $O(n^2 imes k)$로 시간 초과가 발생합니다. (n=200,000)
• Li Chao Tree 도입: DP의 전이 과정에서 $max_{t} (dp[j-1][t] + (sum_{p=t+1}^i a_p)^2)$를 효율적으로 계산하기 위해 Li Chao Tree를 사용합니다. 여기서 합은 접두사 합으로 표현 가능하며, 이는 $dp[j-1][t] + (P[i] - P[t])^2$ 형태가 됩니다. 이 식을 전개하면 $t$에 대한 선형 함수 형태($m cdot P[i] + b$)로 만들 수 있고, Li Chao Tree를 이용하면 삽입 및 쿼리 시간을 $O(log( ext{range of sums}))$으로 줄여 전체 DP 시간 복잡도를 $O(k imes n log( ext{range of sums}))$으로 개선합니다.
• BigInt 사용: 합과 스코어 계산 시 발생할 수 있는 오버플로우를 방지하기 위해 JavaScript의 BigInt를 사용합니다.

개발 임팩트

이 기법은 $O(N^2)$ 이상의 복잡도를 가지는 DP 문제를 $O(N log N)$ 또는 $O(N log W)$ (W는 값의 범위) 수준으로 최적화할 수 있는 강력한 방법을 제시합니다. 이는 대규모 데이터셋에서의 성능 최적화에 필수적이며, 알고리즘 설계 및 문제 해결 능력 향상에 기여합니다.

커뮤니티 반응

(제공된 원문에는 커뮤니티 반응에 대한 언급이 없습니다.)