배열 패턴 — 투포인터 · 슬라이딩윈도우 · 이진탐색 · 프리픽스섬 · 머지인터벌
같은 배열 하나로 다섯 패턴의 '인덱스를 움직이는 규칙'을 차례로 실행해, 각 패턴이 무엇을 전제로 무엇을 버는지 비교한다.
1 / 12정렬 배열 [2, 4, 6, 8, 10, 12] 하나로 네 패턴을, 구간 목록으로 다섯째 패턴을 봅니다. 패턴이란 '인덱스를 움직이는 규칙'입니다 — 규칙이 복잡도를 정합니다.
투 포인터슬라이딩 윈도우이진 탐색프리픽스 섬머지 인터벌
24681012
단계 목록 · 키보드 ←/→ 이동, Space 재생
다섯 패턴의 정체는 '무엇을 전제로 무엇을 안 하는가'다 — 정렬을 전제로 후보를 지우고(투 포인터·이진), 연속성을 전제로 다시 계산하지 않고(윈도우·프리픽스), 정렬 후엔 이웃만 본다(인터벌).
왜 헷갈리는가
문제를 보고 패턴이 안 떠오르는 것은 패턴을 '코드 모양'으로 외웠기 때문이다. 각 패턴이 죽이는 낭비(중복 재계산, 무의미한 후보)를 알면 문제 문장에서 신호가 보인다 — '정렬된', '연속 부분', '구간 합', '겹침'.
패턴별 신호와 규칙
문제 문장 속 신호 → 패턴.
- "정렬된 배열에서 두 수의 합/조건 쌍" → 투 포인터: 양끝에서 수렴, 매 비교가 한 줄을 지운다. O(n)·공간 O(1).
- "연속 부분배열/부분문자열의 최대·최소·개수" → 슬라이딩 윈도우: 나간 것 빼고 들어온 것만 더한다. 재계산 0.
- "정렬(또는 단조 조건)에서 찾기/최솟값 찾기" → 이진 탐색: 절반 버리기. '답을 이진 탐색'(가능/불가능의 경계)까지가 완전체.
- "구간 합 질의가 많다" → 프리픽스 섬: 전처리 O(n) 후 질의 O(1). 2차원·차이 배열로 확장.
- "구간들의 겹침/병합/개수" → 머지 인터벌: 시작점 정렬 후 '현재 끝 vs 다음 시작'만 비교.
현업에서의 같은 패턴
이 패턴들은 코딩 테스트 전유물이 아니다. 슬라이딩 윈도우는 레이트 리미터와 이동 평균 모니터링의 뼈대고, 프리픽스 섬은 OLAP의 누적 집계·세그먼트 트리의 기초며, 머지 인터벌은 회의실 예약·IP 대역 정리·가용 시간 계산에 그대로 쓰인다. 이진 탐색은 '롤백할 커밋 찾기'(git bisect)라는 형태로 매일 쓰인다.
기억할 것
- 패턴 = 낭비를 죽이는 규칙. 코드 모양이 아니라 '무엇을 안 하는가'로 기억하라.
- 정렬·단조가 보이면 절반 또는 한 줄을 지울 수 있다(이진·투 포인터).
- 연속 구간이 보이면 재계산을 지울 수 있다(윈도우·프리픽스).
- 구간 문제의 첫 수는 거의 항상 '시작점 정렬'이다.