Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 겹치지 않는 두 하위 리스트의 최대 합 구하는 프로그램

문제 정의

숫자로 이루어진 리스트 nums와 두 개의 값 x, y가 주어졌다고 가정해 보겠습니다. 이때 길이가 각각 x와 y이면서 서로 겹치지 않는 두 하위 리스트(sublist)의 최대 합을 구해야 합니다.

예를 들어 입력이 nums = [3, 2, 10, -2, 7, 6], x = 3, y = 1이라면 결과는 22가 됩니다. 길이가 3인 하위 리스트로는 [3, 2, 10](합계 15)을 선택하고, 나머지 하나로는 [7](합계 7)을 선택하면 15 + 7 = 22가 되기 때문입니다.

풀이 접근 방법

이 문제는 누적 합(prefix sum) 기법을 활용하면 효율적으로 해결할 수 있습니다. 먼저 누적 합 배열을 만들어 임의 구간의 합을 상수 시간에 계산할 수 있게 하고, 한쪽 구간의 "시작 지점까지의 최대 합"을 미리 누적해 두면 다른 구간의 위치를 한 번의 반복으로 순회하며 최댓값을 찾을 수 있습니다.

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

  • P를 원소 0 하나만 가진 리스트로 초기화한 뒤, A의 각 원소 x에 대해 (P의 마지막 원소 + x)를 P의 끝에 추가하여 누적 합 배열을 만듭니다.
  • solve() 함수를 정의합니다. 이 함수는 len1과 len2를 인자로 받습니다.
  • Q를 각 i(0부터 len(P) − len1 − 1 범위)에 대해 P[i + len1] − P[i]를 원소로 갖는 리스트로 구성합니다. 즉, 길이가 len1인 모든 연속 구간의 합 목록입니다.
  • prefix를 Q의 복사본으로 만든 뒤, i를 0부터 len(prefix) − 2까지 순회하며 prefix[i + 1]을 prefix[i + 1]과 prefix[i] 중 큰 값으로 갱신합니다. 이 과정을 거치면 prefix[i]는 "인덱스 i 이전 영역에서 얻을 수 있는 길이 len1 구간 합의 최댓값"이 됩니다.
  • ans를 음의 무한대(-inf)로 초기화합니다.
  • i를 len1부터 len(P) − len2 − 1까지 순회하며 다음을 반복합니다.
    • left := prefix[i − len1] → 앞쪽에 놓인 길이 len1 구간의 최대 합
    • right := P[i + len2] − P[i] → 현재 위치 i에서 시작하는 길이 len2 구간의 합
    • ans := ans와 (left + right) 중 큰 값으로 갱신
  • ans를 반환합니다.
  • 메인 메서드에서는 solve(len1, len2)와 solve(len2, len1) 중 더 큰 값을 최종 결과로 반환합니다. 긴 구간과 짧은 구간의 배치 순서(앞/뒤)에 따라 최적해가 달라질 수 있으므로 두 경우를 모두 확인해야 합니다.

예제 구현

아래 구현을 통해 더 자세히 이해해 보겠습니다.

class Solution:
    def solve(self, A, len1, len2):
        # 누적 합(prefix sum) 배열 생성
        P = [0]
        for x in A:
            P.append(P[-1] + x)

        def solve(len1, len2):
            # 길이가 len1인 모든 연속 구간의 합 계산
            Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]

            # prefix[i]: 인덱스 i 이전 영역에서의 최대 구간 합
            prefix = Q[:]
            for i in range(len(prefix) - 1):
                prefix[i + 1] = max(prefix[i + 1], prefix[i])

            ans = float("-inf")
            # 길이 len2 구간의 시작 위치를 이동하며 최댓값 탐색
            for i in range(len1, len(P) - len2):
                left = prefix[i - len1]      # 앞쪽 구간의 최대 합
                right = P[i + len2] - P[i]   # 뒤쪽 구간의 합
                ans = max(ans, left + right)
            return ans

        # 두 구간의 배치 순서(앞/뒤)를 바꿔 두 경우 모두 확인
        return max(solve(len1, len2), solve(len2, len1))


ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))

입력

[3, 2, 10, -2, 7, 6], 3, 1

출력

22

복잡도 분석

누적 합 배열 생성에 O(n), 각 방향(len1 → len2, len2 → len1)의 탐색에 각각 O(n)이 소요되므로 전체 시간 복잡도는 O(n)입니다. 가능한 모든 구간 조합을 이중 반복문으로 검사하는 완전 탐색(O(n²))보다 훨씬 효율적이며, 공간 복잡도 역시 누적 합 배열과 prefix 배열 저장을 위해 O(n)입니다.