문제 정의
숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 리스트의 시작과 끝이 서로 이어져 있다고 생각하면, 이 리스트를 하나의 원형(circular) 리스트로 볼 수 있습니다. 우리가 구해야 할 것은 이 원형 리스트에서 비어 있지 않은 부분 리스트(sublist) 중 합이 가장 큰 값을 찾는 것입니다.
예를 들어 입력이 nums = [2, 3, -7, 4, 5]라면 출력은 14가 됩니다. 원형 구조 덕분에 [4, 5, 2, 3]처럼 리스트 끝에서 시작 부분으로 넘어가는 부분 리스트를 선택할 수 있고, 그 합이 4 + 5 + 2 + 3 = 14로 최대이기 때문입니다.
풀이 접근 방법: 카데인 알고리즘 두 번 적용
이 문제는 유명한 카데인 알고리즘(Kadane's Algorithm)을 두 번 사용하면 선형 시간에 해결할 수 있습니다. 핵심 아이디어는 최대 합을 가지는 부분 리스트가 다음 두 경우 중 하나에 반드시 속한다는 점입니다.
- 경계를 넘지 않는 경우: 일반적인 최대 부분 배열 문제와 동일하게 카데인 알고리즘으로 구합니다. (max_sum)
- 경계를 넘는 경우: 시작과 끝을 모두 포함해야 하므로, 전체 합에서 최소 부분 배열의 합(min_sum)을 빼면 됩니다. 즉, sum(nums) − min_sum이 후보 값이 됩니다.
두 후보 값 중 더 큰 것이 최종 정답입니다.
알고리즘 단계
- max_sum := −∞(음의 무한대), cur_max := 0으로 초기화
- min_sum := +∞(양의 무한대), cur_min := 0으로 초기화
- nums의 각 요소 num에 대해 반복:
- cur_max := max(num, cur_max + num)
- max_sum := max(max_sum, cur_max)
- cur_min := min(num, cur_min + num)
- min_sum := min(min_sum, cur_min)
- 만약 max_sum ≤ 0이면(모든 원소가 음수인 경우), '전체 합 − 최소 합' 방식은 잘못된 결과를 내므로 그대로 max_sum을 반환
- 그렇지 않으면 max(max_sum, sum(nums) − min_sum)을 반환
예제 코드
import math class Solution: def solve(self, nums): max_sum = -math.inf cur_max = 0 min_sum = math.inf cur_min = 0 for num in nums: cur_max = max(num, cur_max + num) max_sum = max(max_sum, cur_max) cur_min = min(num, cur_min + num) min_sum = min(min_sum, cur_min) if max_sum <= 0: return max_sum return max(max_sum, sum(nums) - min_sum) ob = Solution() nums = [2, 3, -7, 4, 5] print(ob.solve(nums))
입력
[2, 3, -7, 4, 5]
출력
14
동작 원리 살펴보기
위 예제에서 전체 합은 2 + 3 − 7 + 4 + 5 = 7이고, 최소 부분 배열은 [-7]이므로 그 합은 −7입니다. 따라서 경계를 넘는 경우의 후보 값은 7 − (−7) = 14가 됩니다. 한편 경계를 넘지 않는 최대 부분 배열은 [4, 5]로 합이 9입니다. 두 후보 중 더 큰 값인 14가 최종 답이 됩니다.
시간 및 공간 복잡도
리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 변수는 상수 개수뿐이므로 공간 복잡도는 O(1)입니다. 이는 모든 가능한 부분 리스트를 완전 탐색하는 O(n²) 이상의 방법보다 훨씬 효율적입니다.