Python으로 배열의 모든 홀수 길이 부분 배열 합 구하기

문제 개요

양수로만 이루어진 배열 nums가 주어졌을 때, 가능한 모든 홀수 길이 부분 배열(subarray)의 합을 구하는 프로그램을 만들어 보겠습니다. 여기서 부분 배열이란 원본 배열에서 연속된 요소들로 구성된 부분 수열을 의미합니다. 즉, 길이가 1, 3, 5처럼 홀수인 모든 연속 구간의 합을 모두 더하는 것이 목표입니다.

예제 살펴보기

예를 들어 입력이 nums = [3, 8, 2, 5, 7]이라면, 홀수 길이를 가지는 부분 배열은 다음과 같습니다.

nums[0] = 3
nums[1] = 8
nums[2] = 2
nums[3] = 5
nums[4] = 7
nums[0..2] → 합 = 13
nums[1..3] → 합 = 15
nums[2..4] → 합 = 14
nums[0..4] → 합 = 25

따라서 전체 합은 3 + 8 + 2 + 5 + 7 + 13 + 15 + 14 + 25 = 92가 됩니다.

해결 접근 방법

이 문제는 브루트 포스 방식으로 해결할 수 있습니다. 먼저 가능한 모든 홀수 길이(1, 3, 5, ...)를 구한 뒤, 각 길이별로 시작 위치를 이동하면서 해당 구간의 합을 누적하는 방식입니다. 구체적인 단계는 다음과 같습니다.

total을 0으로 초기화합니다.
idx를 0으로 초기화합니다.
l에 1, 3, 5처럼 홀수인 길이 값들을 담은 리스트를 저장합니다.
idx가 l의 크기보다 작은 동안 다음을 반복합니다.
- k := l[idx]로 현재 검사할 부분 배열의 길이를 가져옵니다.
- i를 0부터 nums의 크기까지 반복하면서,
  - i + k < len(nums) + 1 조건을 만족하면(즉, 구간이 배열 범위를 벗어나지 않으면), total에 nums[i]부터 nums[i+k-1]까지의 합을 더합니다.
- idx를 1 증가시킵니다.
모든 반복이 끝나면 total을 반환합니다.

Python 구현 예제

더 나은 이해를 위해 아래의 실제 구현 코드를 살펴보겠습니다.

def solve(nums):
    total = 0
    idx = 0
    l = [i for i in range(len(nums)+1) if i % 2 != 0]

    while(idx < len(l)):
        k = l[idx]
        for i in range(len(nums)):
            if i + k < len(nums) + 1:
                total += sum(nums[i:i+k])
        idx += 1
    return total

nums = [3, 8, 2, 5, 7]
print(solve(nums))

입력

[3, 8, 2, 5, 7]

출력

복잡도 분석 및 최적화 팁

이 알고리즘은 각 홀수 길이마다 모든 시작 위치를 순회하고 슬라이싱 합을 계산하므로, 시간 복잡도는 대략 O(n³)입니다. 공간 복잡도는 홀수 길이 리스트를 저장하는 데 O(n)이 필요합니다.

참고로, 각 요소가 홀수 길이 부분 배열에 포함되는 횟수를 수학적으로 계산하면 O(n) 시간에 최적화할 수 있습니다. 인덱스 i의 요소를 포함하는 부분 배열의 시작 위치는 i+1가지, 끝 위치는 n-i가지이므로, 이를 포함하는 홀수 길이 부분 배열의 개수는 ((i+1) * (n-i) + 1) // 2가 됩니다. 이 값을 각 요소에 곱해 모두 더하면 훨씬 빠르게 같은 결과를 얻을 수 있습니다.