파이썬 코딩테스트 강좌, 슬라이딩 윈도우

컴퓨터 과학에서 알고리즘 문제는 우리에게 문제를 해결하기 위한 효율적인 방법을 제공하는 중요한 요소입니다.
그중에서도 슬라이딩 윈도우 기법은 배열이나 문자열과 같은 선형 데이터 구조에서 특정 조건을 만족하는 연속적인 부분 배열을 찾는 데 사용됩니다.
이번 강좌에서는 슬라이딩 윈도우 기법을 활용한 문제를 한 가지 풀어보며, 이 기법이 어떤 방식으로 문제를 해결하는 데 유용한지 살펴보겠습니다.

문제 설명

주어진 정수 배열 nums와 정수 k에 대해 k의 크기를 가지는 부분 배열 중 최대 합을 가진 부분 배열의 합을 구하시오.
즉, 연속적으로 k개 요소의 합을 최대화하는 문제입니다.
예를 들어, 배열 nums = [1, 3, 2, 5, 4, 8]이고 k = 3일 때,
부분 배열 [5, 4, 8]의 합이 가장 크므로 답은 17이 됩니다.

문제 요구 사항

함수의 입력: 정수 배열 nums와 정수 k
함수의 출력: 최대 부분 배열의 합

문제 접근 방법

이 문제를 슬라이딩 윈도우 기법을 사용하여 풀면, 입력 배열을 한 번만 순회하여 시간 복잡도를 O(n)으로 줄일 수 있습니다.
본 기법의 아이디어는 두 개의 포인터를 사용하여 현재 윈도우의 시작과 끝을 조절하여, 부분 배열의 합을 계산하는 것입니다.

슬라이딩 윈도우 기법 설명

초기 윈도우를 정의합니다. 포인터를 이용하여 첫 번째 k개의 요소를 선택하고 이들의 합을 계산합니다.
그 후, 두 번째 윈도우로 이동하면서 윈도우의 시작 부분에서 하나의 요소를 제거하고 끝 부분에 하나의 요소를 추가합니다.
이 과정을 배열의 끝까지 반복합니다.
각 단계에서 얻은 윈도우의 합을 기록하고, 이전에 기록한 최대 합과 비교하여 최대 합을 업데이트합니다.

코드 구현


def max_sum_subarray(nums, k):
    # 초기 윈도우 계산
    max_sum = sum(nums[:k])
    window_sum = max_sum
    
    # 슬라이딩 윈도우 적용
    for i in range(k, len(nums)):
        # 현재 윈도우에서 가장 왼쪽 숫자를 제거하고 새로 추가된 숫자를 더합니다.
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# 예제 실행
nums = [1, 3, 2, 5, 4, 8]
k = 3
result = max_sum_subarray(nums, k)
print(f"최대 부분 배열의 합: {result}")

코드 설명

위의 함수 max_sum_subarray는 배열 nums와 정수 k를 인자로 받아 최대 합을 반환합니다.
먼저, 초기 윈도우의 합을 구한 후 슬라이딩 윈도우 방식을 통해 배열을 순회합니다.
각 윈도우의 합은 이전 합에서 가장 왼쪽 요소를 제거하고 새 요소를 추가하여 구하고,
각 윈도우의 합을 기록하여 최대 합을 업데이트합니다.

결과 및 테스트

위의 예제를 실행하면 최대 부분 배열의 합: 17이라는 결과가 출력됩니다.
이처럼 슬라이딩 윈도우 기법을 활용하면 한 번의 순회만으로 빠르게 문제를 해결할 수 있습니다.

마무리

이번 강좌에서는 슬라이딩 윈도우 기법을 활용하여 배열에서 최대 부분 합을 구하는 문제를 해결했습니다.
이 기법은 동일한 요소를 반복해서 비교할 필요 없이 전체 배열을 단 한 번만 순회하여 시간 복잡도를 줄일 수 있어 매우 유용합니다.
여러 다른 문제에서도 활용할 수 있으므로, 실전 코딩 테스트와 알고리즘 문제가 빈번히 출제되는 분야에서 큰 도움이 될 것입니다.