투 포인터가 가능한 문제 판별법 (체크리스트)

아래 조건 중 3개 이상 맞으면 거의 확정

---

1️⃣ “연속한 구간(부분 수열)”이라는 말이 있는가?

투 포인터의 절대적 전제 조건

✔ 연속한
✔ 부분 수열
✔ subarray
✔ 구간 [L, R]

❌ 순열, 조합, 임의 선택 → 투 포인터 아님

---

2️⃣ 구간에 대한 “조건”이 단조적인가?

🔑 단조성(monotonicity)이 핵심

오른쪽을 늘리면 조건이 점점 나빠지거나 / 좋아지거나

예시

조건	단조성
합 ≤ K	right ↑ → 합 ↑
중복 없음	right ↑ → 중복 가능성 ↑
서로 다른 수 개수 ≤ K	right ↑ → 개수 ↑
최대 − 최소 ≤ K	right ↑ → 차이 ↑

👉 조건이 깨지면 left를 움직여 회복 가능

---

3️⃣ “최대 / 최소 / 개수”를 묻는가?

투 포인터의 전형적인 질문들:

✔ 가능한 최대 길이
✔ 가능한 최소 길이
✔ 조건을 만족하는 구간의 개수

이 중 하나면 의심 1단계 통과

---

4️⃣ N이 크다 (보통 ≥ 10⁵)

이건 거의 신호등 🚦

N가능	알고리즘
10³	O(N²)
10⁵	O(N) or O(N log N)
10⁶	거의 O(N)

👉 연속 + 조건 + N 큼 → 투 포인터 거의 확정

---

5️⃣ “하나씩 늘려보면 된다”는 느낌이 드는가?

문제를 읽을 때 이런 생각이 들면 바로 투 포인터:

• “오른쪽을 늘리다가 안 되면 왼쪽 줄이면 되겠네”
• “중복 나오면 앞(left)에서 빼면 되겠네”
• “합이 넘치면 앞(left)에서 줄이면 되겠네”

👉 이 생각 자체가 투 포인터 사고방식

---

❌ 투 포인터가 절대 안 되는 경우

🚫 1. 연속이 아니다

 

수열에서 K개를 골라서

❌ 투 포인터 불가

---

🚫 2. 조건이 비단조적

 

합이 정확히 K

합은:

• 늘리면 커졌다가
• 줄이면 작아졌다가
• 다시 늘리면 또 커짐

👉 슬라이딩 윈도우 불가

(단, 양수만 있을 때는 예외적으로 가능)

---

🚫 3. 뒤에서 상태가 바뀌는 문제

 

나중 선택이 앞의 상태를 바꾼다

👉 DP / 그리디 / 스택 문제

---

🔍 대표 문제 유형 매핑

문제 설명	알고리즘
중복 없는 연속 부분 수열 개수	투 포인터
합이 K 이하인 최대 길이	투 포인터
서로 다른 수 ≤ K	투 포인터
최소 길이 부분 수열	투 포인터
스카이라인 / 히스토그램	❌ 스택
스위치 / 토글	❌ 그리디
모든 경우의 수	❌ DP

---

🧠 빠른 판별 3문장 법칙

문제 보자마자 스스로에게 물어볼 질문

1️⃣ 연속인가?
2️⃣ 오른쪽 늘리면 조건이 단조적으로 변하나?
3️⃣ 안 되면 왼쪽 줄이면 회복되나?

👉 전부 YES → 투 포인터

---

📌 한 줄 요약

연속 + 조건 단조 + N 큼
👉 투 포인터