"Arrays 트랙에서 투 포인터랑 슬라이딩 윈도우를 만났어. 이제 그게 진짜 뭔지 봐: 배열 트릭이 아니라, 한 아이디어를 위한 일반 패러다임 — 점진적으로 움직이고 다시 계산하는 대신 일을 재사용."
트릭에서 패러다임으로
Arrays 트랙에선 특정 기법처럼 느껴졌어. 한발 물러서면 그건 패러다임이야 — 많은 O(n²) 무차별을 O(n) 으로 바꾸는 재사용 가능한 전략. 공유 원칙: 겹치는 일을 다시 계산하는 중첩 반복문 대신, 작은 상태 (포인터 둘, 또는 윈도우의 누적 요약) 를 유지하고 전진하며 점진적으로 업데이트. 각 단계가 O(1) 이라, 전체 패스가 O(n). 한 문제를 외우는 게 아니라 패러다임을 알아보는 게 새 상황에 적용하게 해.
투 포인터, 일반화
투 포인터는 두 위치가 협응해 움직여 모든 쌍 확인을 피할 때마다 적용돼. 수렴 (끝이 안으로): 정렬 배열 쌍-합, 회문 확인, 물-가장-많이-가두기, 퀵소트 분할 단계. 같은 방향 / 빠른-느린: 연결 리스트 순환 검출, 제자리 중복 제거, 정렬된 두 수열 병합. 공통 신호: 한 구조 (또는 정렬된 둘) 위 중첩 반복문을 쓰려 유혹받고, 위치 사이 관계가 대부분 쌍을 건너뛰게 해. 3sum 이 정석 업그레이드 — 정렬하고, 각 원소마다 투-포인터 스캔, O(n³) 를 O(n²) 으로.
슬라이딩 윈도우, 일반화
슬라이딩 윈도우는 수열이나 스트림 위 '속성 만족하는 최선/최장/최단 연속 구간' 어디에든 적용돼. 윈도우 [left, right] 랑 누적 요약 (합, 문자 개수, 최대) 을 유지; right 가 전진하며 새 원소를 더하고, 윈도우가 속성을 어기면 left 에서 줄여. 두 포인터 다 앞으로만 움직여서, 중첩처럼 보여도 O(n). '중복 없는 가장 긴 부분 문자열', '합 ≥ target 인 가장 작은 부분배열', 속도 제한, 스트리밍 분석을 굴려. 윈도우는 그냥 두 포인터 + 그 사이의 유지된 요약이야.
투 포인터랑 슬라이딩 윈도우는 배열 트릭이 아니라 패러다임: 작은 상태를 유지하고 위치가 전진하며 점진적으로 업데이트, 그래서 겹침을 절대 다시 계산 안 해. 둘 다 O(n²) 를 O(n) 으로. 신호: '정렬 데이터의 쌍' / '두 수열 병합' (투 포인터); '속성 X 인 최선 연속 구간' (슬라이딩 윈도우).
피파의 고백
난 투 포인터를 '배열 문제' 폴더에 넣고 연결 리스트에 쓸 생각을 안 했어 — 플로이드 순환 검출이 거기서도 빠른/느린 포인터를 보여주기 전까진. 아빠가 관통선에 이름 붙였어: "배열에 관한 게 아니야. '점진적으로 움직여, 다시 계산하지 마' 야." 예시 대신 패러다임을 쥐니, 스트림, 문자열, 리스트에서 똑같이 윈도우랑 포인터-쌍을 보기 시작했어. 예시는 문이고; 패러다임은 방이야.
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]))
lo += 1; 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) 정렬 배열에서 target 으로 합쳐지는 두 수 찾기, (2) 최대 2 개 구별 문자 담는 가장 긴 부분 문자열, (3) 정렬된 두 리스트를 하나로 병합. 그다음 셋 다 공유하는, O(n²) 아니라 O(n) 으로 만드는 단일 원칙을 말해.
Hint
(1) 투 포인터 (정렬 데이터에 수렴); (2) 슬라이딩 윈도우 (속성 가진 가장 긴 연속 구간); (3) 투 포인터 (리스트당 하나, 더 작은 앞을 전진). 공유 원칙: 점진적 상태 유지하고 포인터를 앞으로만 전진, 겹치는 부분 문제를 다시 계산하는 대신 앞 일을 재사용 — O(n).
Progress
Progress is local-only — sign in to sync across devices.