컴퓨터 과학에서 알고리즘 문제는 우리에게 문제를 해결하기 위한 효율적인 방법을 제공하는 중요한 요소입니다.
그중에서도 슬라이딩 윈도우 기법은 배열이나 문자열과 같은 선형 데이터 구조에서 특정 조건을 만족하는 연속적인 부분 배열을 찾는 데 사용됩니다.
이번 강좌에서는 슬라이딩 윈도우 기법을 활용한 문제를 한 가지 풀어보며, 이 기법이 어떤 방식으로 문제를 해결하는 데 유용한지 살펴보겠습니다.
문제 설명
주어진 정수 배열 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이라는 결과가 출력됩니다.
이처럼 슬라이딩 윈도우 기법을 활용하면 한 번의 순회만으로 빠르게 문제를 해결할 수 있습니다.
마무리
이번 강좌에서는 슬라이딩 윈도우 기법을 활용하여 배열에서 최대 부분 합을 구하는 문제를 해결했습니다.
이 기법은 동일한 요소를 반복해서 비교할 필요 없이 전체 배열을 단 한 번만 순회하여 시간 복잡도를 줄일 수 있어 매우 유용합니다.
여러 다른 문제에서도 활용할 수 있으므로, 실전 코딩 테스트와 알고리즘 문제가 빈번히 출제되는 분야에서 큰 도움이 될 것입니다.