문제 소개
숫자 목록 nums가 원형으로 연결된 순환 리스트(circular list)를 나타낸다고 가정해 봅시다. 이때 서로 인접하지 않은 숫자들을 골라 만들 수 있는 최대 합을 구하는 것이 목표입니다.
예를 들어 입력이 nums = [10, 3, 4, 8]이라면 결과는 14가 됩니다. 10과 4를 선택하면 되는데, 10과 8은 순환 구조상 서로 인접해 있기 때문에 함께 선택할 수 없습니다.
해결 접근 방법
순환 리스트의 핵심 특징은 첫 번째 요소와 마지막 요소가 서로 인접한다는 점입니다. 따라서 이 문제를 다음 두 가지 독립적인 경우로 나누어 생각할 수 있습니다.
- 경우 1: 마지막 요소를 제외한 리스트(nums[0] ~ nums[n-2])에서 인접하지 않은 요소의 최대 합을 구합니다. 즉, 첫 번째 요소를 선택할 수 있는 경우입니다.
- 경우 2: 첫 번째 요소를 제외한 리스트(nums[1] ~ 끝)에서 인접하지 않은 요소의 최대 합을 구합니다. 즉, 마지막 요소를 선택할 수 있는 경우입니다.
두 경우 중 더 큰 값이 최종 정답이 됩니다. 각 경우는 일반적인 선형 리스트에서 인접하지 않은 요소의 최대 합을 구하는 잘 알려진 '하우스 로버(House Robber)' 유형의 문제와 동일합니다.
알고리즘 단계
- n := nums의 길이
- nums1 := nums[0]부터 nums[n-2]까지 (마지막 요소 제외)
- nums2 := nums[1]부터 끝까지 (첫 번째 요소 제외)
- 재귀 함수 f(i) 정의 — nums1에 대해 계산:
- i가 nums1의 길이 이상이면 0을 반환
- 그렇지 않으면 max(nums1[i] + f(i + 2), f(i + 1))을 반환
- 재귀 함수 g(j) 정의 — nums2에 대해 계산:
- j가 nums2의 길이 이상이면 0을 반환
- 그렇지 않으면 max(nums2[j] + g(j + 2), g(j + 1))을 반환
- 메인 로직에서 max(f(0), g(0))을 반환
여기서 f(i + 2)는 현재 위치의 값을 선택하고 다다음 위치로 건너뛰는 경우를, f(i + 1)은 현재 위치의 값을 선택하지 않고 다음 위치로 넘어가는 경우를 의미합니다.
구현 예제
class Solution:
def solve(self, nums):
n = len(nums)
nums1 = nums[: n - 1]
nums2 = nums[1:]
def f(i):
if i >= len(nums1):
return 0
return max(nums1[i] + f(i + 2), f(i + 1))
def g(j):
if j >= len(nums2):
return 0
return max(nums2[j] + g(j + 2), g(j + 1))
return max(f(0), g(0))
ob = Solution()
nums = [10, 3, 4, 8]
print(ob.solve(nums))
입력
[10, 3, 4, 8]
출력
14
복잡도 분석 및 개선점
위 재귀 풀이는 동일한 하위 문제를 여러 번 중복 계산하므로 최악의 경우 지수 시간 복잡도를 가질 수 있습니다. 실전에서는 메모이제이션(memoization)을 적용하거나 반복문 기반의 동적 계획법(DP)으로 변환하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다.