[Daily morning study] 슬라이딩 윈도우 / 투 포인터 기법
in Daily morning study / DSA
#daily morning study
슬라이딩 윈도우 (Sliding Window)
핵심 아이디어
배열이나 문자열에서 연속된 부분 구간(window)을 순회할 때, 매번 처음부터 다시 계산하는 대신 이전 결과에 “들어오는 원소를 더하고, 빠지는 원소를 빼는” 방식으로 O(n)에 해결하는 기법이다.
브루트 포스로 구간 합을 구하면 O(n²)이지만, 슬라이딩 윈도우를 쓰면 O(n)으로 줄어든다.
고정 크기 윈도우
윈도우 크기 k가 고정되어 있는 경우다.
def max_sum_subarray(arr: list[int], k: int) -> int:
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # 오른쪽 추가, 왼쪽 제거
max_sum = max(max_sum, window_sum)
return max_sum
# 예시: [2, 1, 5, 1, 3, 2], k=3 → 9 (5+1+3)
가변 크기 윈도우
조건을 만족하는 가장 짧은/긴 구간을 찾을 때 사용한다. 두 포인터 left, right로 윈도우 경계를 관리한다.
# 합이 target 이상인 최소 길이 부분 배열
def min_subarray_len(target: int, nums: list[int]) -> int:
left = 0
window_sum = 0
min_len = float('inf')
for right in range(len(nums)):
window_sum += nums[right]
while window_sum >= target:
min_len = min(min_len, right - left + 1)
window_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0
right를 한 칸씩 확장하고, 조건을 만족하면 left를 좁혀가며 최솟값을 갱신한다.
대표 문제 유형
- 길이 k인 부분 배열의 최대/최소 합
- 중복 없는 가장 긴 부분 문자열 (Longest Substring Without Repeating Characters)
- 합이 특정 값 이상인 최소 길이 부분 배열
투 포인터 (Two Pointers)
핵심 아이디어
배열이나 리스트에서 두 개의 포인터를 이용해 O(n²) 탐색을 O(n)으로 줄이는 기법이다. 슬라이딩 윈도우가 “연속 구간”에 집중한다면, 투 포인터는 정렬된 배열에서 두 원소의 조합을 찾는 데 더 자주 쓰인다.
양끝 수렴 방식
정렬된 배열에서 left=0, right=n-1로 시작해 조건에 따라 포인터를 이동한다.
# 두 수의 합이 target인 인덱스 찾기 (정렬된 배열)
def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int]:
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return (left, right)
elif s < target:
left += 1 # 합이 작으면 왼쪽 포인터 증가
else:
right -= 1 # 합이 크면 오른쪽 포인터 감소
return (-1, -1)
같은 방향 이동 방식
두 포인터가 같은 방향으로 이동하면서 조건을 만족하는 구간을 찾는다. 슬라이딩 윈도우와 형태가 비슷하다.
# 정렬된 배열에서 중복 제거 (in-place)
def remove_duplicates(nums: list[int]) -> int:
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
slow는 고유 원소가 채워진 마지막 위치, fast는 탐색 포인터다.
대표 문제 유형
- Two Sum (정렬된 배열)
- 세 수의 합이 0인 조합 (3Sum)
- 팰린드롬 판별
- 정렬된 배열에서 중복 제거
- 물통 문제 (Container With Most Water)
슬라이딩 윈도우 vs 투 포인터 비교
| 구분 | 슬라이딩 윈도우 | 투 포인터 |
|---|---|---|
| 주요 목적 | 연속 구간의 합/최댓값/조건 | 두 원소의 조합/조건 |
| 배열 정렬 필요 여부 | 불필요 | 양끝 수렴 방식은 필요 |
| 포인터 이동 방향 | 같은 방향 (오른쪽으로) | 양방향 or 같은 방향 |
| 시간 복잡도 | O(n) | O(n) |
실제로 두 기법은 겹치는 부분이 많다. 가변 크기 슬라이딩 윈도우는 투 포인터의 한 형태라고 볼 수 있다.
슬라이딩 윈도우 응용: 최장 반복 문자 교체
# 최대 k번 문자 교체로 만들 수 있는 가장 긴 같은 문자 부분 문자열
def character_replacement(s: str, k: int) -> int:
count = {}
left = 0
max_count = 0
result = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
max_count = max(max_count, count[s[right]])
# 윈도우 크기 - 최빈 문자 개수 > k 이면 윈도우 축소
if (right - left + 1) - max_count > k:
count[s[left]] -= 1
left += 1
result = max(result, right - left + 1)
return result
투 포인터 응용: 3Sum
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # 중복 스킵
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return result
복잡도 정리
| 기법 | 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 브루트 포스 구간 탐색 | O(n²) | O(1) |
| 고정 크기 슬라이딩 윈도우 | O(n) | O(1) |
| 가변 크기 슬라이딩 윈도우 | O(n) | O(k) (해시맵 사용 시) |
| 투 포인터 (정렬 포함) | O(n log n) | O(1) |
문제 풀 때 판단 기준
- “연속 구간” 키워드가 보이면 → 슬라이딩 윈도우
- “정렬된 배열에서 두/세 원소의 합” 키워드가 보이면 → 투 포인터 (양끝 수렴)
- “중복 제거” 또는 “느린/빠른 포인터” 패턴 → 투 포인터 (같은 방향)
- O(n) 안에 해결해야 하고 배열을 한 번만 순회해야 한다면 두 기법 중 하나를 우선 고려
