Python으로 리스트에서 인접하지 않은 요소의 최대 합 구하기

숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 우리는 이 리스트에서 서로 인접하지 않은(바로 옆에 붙어 있지 않은) 숫자들을 선택하여 얻을 수 있는 최대 합을 반환하는 함수를 작성하려고 합니다. 이때 리스트에는 0이나 음수도 포함될 수 있습니다.

예를 들어 입력이 [3, 5, 7, 3, 6]이라면 출력은 16이 됩니다. 3, 7, 6을 선택하면 세 숫자가 서로 인접하지 않으면서 합이 16으로, 가능한 모든 조합 중 가장 크기 때문입니다.

문제 해결 접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 O(n) 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 리스트를 한 번만 순회하면서 각 위치마다 두 가지 상태를 함께 관리하는 것입니다.

• take: 현재 요소를 선택했을 때의 최대 합

• noTake: 현재 요소를 선택하지 않았을 때의 최대 합

구체적인 해결 단계는 다음과 같습니다.

• 리스트의 길이가 2 이하라면, 리스트의 최댓값을 그대로 반환합니다.

• noTake := 0 으로 초기화합니다.

• take := nums[0] 으로 초기화합니다.

• i를 1부터 리스트의 마지막 인덱스까지 반복하며 다음을 수행합니다.

  • take := noTake + nums[i] (현재 요소를 선택하려면 바로 앞의 요소는 반드시 건너뛰어야 하므로)

  • noTake := max(noTake, take) (현재 요소를 건너뛰면 지금까지의 최댓값을 그대로 이어갑니다)

• 반복이 끝나면 max(noTake, take)를 반환합니다.

아래 예제를 통해 더 자세히 이해해 보겠습니다.

예제 코드

class Solution:
   def solve(self, nums):
       if len(nums) <= 2:
           return max(nums)
       noTake = 0
       take = nums[0]
       for i in range(1, len(nums)):
           take, noTake = noTake + nums[i], max(noTake, take)
       return max(noTake, take)

ob = Solution()
nums = [3, 5, 7, 3, 6]
print(ob.solve(nums))

입력

[3, 5, 7, 3, 6]

출력

16

동작 과정 살펴보기

입력 [3, 5, 7, 3, 6]에 대해 알고리즘이 어떻게 진행되는지 단계별로 확인해 보겠습니다.

반복이 종료된 후 max(10, 16)을 계산하므로 최종 결과는 16이 됩니다. 이처럼 매 단계에서 '선택한다'와 '건너뛴다'는 두 가지 경우만 고려하면 되기 때문에, 재귀 호출 없이도 선형 시간 복잡도로 문제를 해결할 수 있습니다.