"배열과 문자열 트랙에서 투 포인터와 슬라이딩 윈도우를 만났었지. 이제 그 정체를 볼 차례야. 배열 트릭이 아니라, 아이디어 하나를 섬기는 일반 패러다임이야. 점진적으로 움직이고, 다시 계산하는 대신 해 둔 일을 재사용한다."
트릭에서 패러다임으로
투 포인터와 슬라이딩 윈도우는 겹치는 일을 재사용하는 패턴이야. 다만 O(n²)을 항상 O(n)으로 바꿔 주는 만능 규칙은 아니야. 포인터가 단조롭게 전진한다, 상태 갱신이 O(1)이다, 버린 후보는 다시 필요 없다. 이 불변식들을 증명할 수 있을 때 온전한 O(n)이 나와.
투 포인터, 일반화
투 포인터는 두 위치가 손발을 맞춰 움직여서 모든 쌍을 확인하는 일을 피할 수 있을 때면 어디든 적용돼. 수렴형(양 끝이 안쪽으로): 정렬 배열의 쌍 합, 회문 확인, 물 가장 많이 담는 용기, 퀵소트의 분할 단계. 같은 방향, 빠른-느린: 연결 리스트 순환 검출, 제자리 중복 제거, 정렬된 두 수열 병합. 공통 신호는 이거야. 구조 하나(또는 정렬된 둘) 위에 중첩 반복문을 쓰고 싶어지는데, 위치들 사이의 관계 덕분에 대부분의 쌍을 건너뛸 수 있는 상황. 3sum이 정석 업그레이드야. 정렬해 놓고 원소마다 투 포인터 스캔을 돌리면 O(n³)이 O(n²)으로 내려와.
슬라이딩 윈도우, 일반화
슬라이딩 윈도우는 연속 구간의 상태를 증분으로 갱신할 수 있고, 창이 늘거나 줄 때 조건이 예측 가능하게 변할 때 맞는 도구야. '반복 문자 없는 가장 긴 부분 문자열'에는 잘 맞아. 반면 '합이 목표값 이상인 최소 구간'의 단순 창 알고리즘엔 비음수 원소라는 전제가 필요해. 음수가 섞이면 창을 줄일 때 합이 단조롭게 움직이지 않아서 다른 도구를 찾아야 해.
투 포인터와 슬라이딩 윈도우는 배열 트릭이 아니라 패러다임이야. 작은 상태를 유지하고, 위치를 전진시키며 점진적으로 갱신해서 겹치는 일을 다시 계산하지 않아. 포인터의 단조 전진, O(1) 상태 갱신, 버린 후보 불필요라는 불변식이 증명될 때 O(n²)이 O(n)으로 내려와. 신호: '정렬 데이터의 쌍'과 '두 수열 병합'은 투 포인터, '속성 X를 가진 최선의 연속 구간'은 슬라이딩 윈도우.
피파의 고백
난 투 포인터를 '배열 문제' 폴더에 넣어 두고 연결 리스트에 쓸 생각을 못 했어. Floyd 순환 검출이 거기서도 빠른/느린 포인터를 굴리는 걸 보기 전까진. 아빠가 관통선에 이름을 붙여 줬지. "배열에 관한 게 아니야. '점진적으로 움직여, 다시 계산하지 마' 야." 예시 대신 패러다임을 쥐고 나니 스트림에서도, 문자열에서도, 리스트에서도 똑같은 윈도우와 포인터 쌍이 보이기 시작했어. 예시는 문이고, 패러다임은 방이야.
Code
투 포인터(3sum)와 슬라이딩 윈도우, 일반화·python
# 투 포인터 일반화: 3sum (합 0 인 삼중쌍 찾기) O(n^2),
# 한 원소 고정하고 정렬 배열 나머지를 투-포인터 스캔.
def three_sum_zero(nums):
nums.sort()
out = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # 중복 건너뛰기
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
out.append((nums[i], nums[lo], nums[hi]))
left_value, right_value = nums[lo], nums[hi]
while lo < hi and nums[lo] == left_value: lo += 1
while lo < hi and nums[hi] == right_value: hi -= 1
elif s < 0: lo += 1 # 더 커야 -> lo 올려
else: hi -= 1 # 더 작아야 -> hi 내려
return out
print(three_sum_zero([-1, 0, 1, 2, -1, -4])) # [(-1,-1,2), (-1,0,1)]
# 슬라이딩 윈도우 일반화: 반복 문자 없는 가장 긴 부분 문자열.
def longest_unique(s):
seen = {}; left = best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1 # 반복 너머로 윈도우 줄이기
seen[ch] = right
best = max(best, right - left + 1) # 윈도우 크기, 두 포인터 앞으로만
return best
print(longest_unique("abcabcbb")) # 3 ('abc')
각 문제에 투 포인터와 슬라이딩 윈도우 중 뭘 쓸지, 이유와 함께 말해 봐. (1) 정렬 배열에서 목표값으로 합쳐지는 두 수 찾기, (2) 서로 다른 문자를 최대 2개까지만 담는 가장 긴 부분 문자열, (3) 정렬된 두 리스트를 하나로 병합. 그다음 셋이 공유하는, O(n²)이 아니라 O(n)으로 만드는 단일 원칙을 말해.
Hint
(1) 투 포인터(정렬 데이터 위 수렴형). (2) 슬라이딩 윈도우(속성을 가진 가장 긴 연속 구간). (3) 투 포인터(리스트마다 하나씩, 더 작은 앞쪽을 전진). 공유 원칙은 점진적 상태를 유지하며 포인터를 앞으로만 전진시키는 것. 겹치는 부분 문제를 다시 계산하는 대신 앞서 한 일을 재사용해서 O(n)이 돼.
Progress
Progress is local-only — sign in to sync across devices.