Two Pointers(투포인터) — “양쪽에서 좁혀가며 O(n)으로 끝내는 기술”

Two Pointers(투포인터) — “양쪽에서 좁혀가며 O(n)으로 끝내는 기술”

코테에서 투포인터는 자주 등장하지만, 핵심은 단순해요.

포인터(인덱스) 2개를 잡고, 둘을 한 방향으로만 움직이면서 정답을 만든다.
그래서 보통 **O(n²)**로 풀리던 문제를 **O(n)**으로 줄여줍니다.

투포인터가 “잘 먹히는” 순간은 딱 하나의 공통점이 있어요.

✅ 한 번 움직인 포인터가 다시 뒤로 돌아갈 필요가 없도록
조건 판단이 **단조(monotonic)**여야 한다는 점입니다.

---

1) 투포인터가 잘 먹히는 대표 패턴 2가지

패턴 A) 정렬 + 양끝 좁히기 (짝 맞추기 / 최소 횟수)

키워드

• “최대 2개씩 묶기”
• “두 수의 합이 limit 이하”
• “최소 보트 수 / 최소 그룹 수 / 최대 매칭”
• 정렬하면 가능한지/불가능한지가 단조가 됨

직관

• “가장 무거운 사람”은 선택지가 거의 없음 → 먼저 처리해야 함
• 무거운 사람을 태울 때, 같이 태울 수 있다면 가장 가벼운 사람을 붙이는 게 최선
• 가벼운 사람과도 같이 못 타면 → 무거운 사람은 누구와도 못 탐 → 혼자 보내는 게 최선

---

2) 대표 문제: 구명보트(최소 보트 수)

문제 요약

• 보트 1대에 최대 2명
• 무게 제한(limit) 초과하면 같이 못 탐
• 모두 구출할 때 필요한 최소 보트 수

풀이 전략(그리디 + 투포인터)

1. 몸무게를 오름차순 정렬
2. L=가벼운 쪽, R=무거운 쪽 포인터
3. 매번 R(가장 무거운 사람)은 보트 1대 확정
4. people[L] + people[R] <= limit이면 같이 태우고 L++
5. R--, 보트 수 +1

---

3) 정답 코드 (Python)

 

def solution(people, limit):

people.sort()

l, r = 0, len(people) - 1

boats = 0

while l <= r: # 가장 무거운 사람(r)은 무조건 태운다 (보트 1대 확정)

if people[l] + people[r] <= limit:

l += 1 # 가장 가벼운 사람도 같이 탈 수 있으면 같이 태움

r -= 1

boats += 1

return boats

---

4) 예시로 이해하기

people = [70, 50, 80, 50], limit = 100
정렬 → [50, 50, 70, 80]

• L=50, R=80 → 130 (불가) → 80 혼자 (boats=1), R--
• L=50, R=70 → 120 (불가) → 70 혼자 (boats=2), R--
• L=50, R=50 → 100 (가능) → 둘이 같이 (boats=3)

정답 = 3

---

5) 왜 이게 최적인가? (한 문장 증명 느낌)

가장 무거운 사람은 늦게 처리할수록 함께 탈 수 있는 후보가 더 줄어든다.
그러니 무거운 사람부터 태우고, 같이 태울 수 있다면 가장 가벼운 사람을 붙이는 것이 항상 손해가 없다.

• 무거운 사람을 가벼운 사람과도 못 묶는다면 → 그 무거운 사람은 누구와도 못 묶음
• 묶을 수 있다면 → “가벼운 사람”을 쓰는 것이 다른 조합을 망치지 않음

---

6) 투포인터를 떠올리는 체크리스트(암기용)

다음 중 하나라도 보이면 투포인터를 의심해요.

• ✅ 정렬 후 “양끝에서 좁히며 짝을 지어 조건 만족”
• ✅ “한 번의 스캔으로 끝낼 수 있게 포인터가 뒤로 갈 필요 없음”
• ✅ “최대/최소 매칭, 최소 횟수” 같은 최적화 + 조건이 단조

---

7) 덤: (주의) 투포인터가 잘 안 되는 케이스

• 연속 구간 합 문제에서 음수가 섞이면 단조가 깨질 수 있어요.
  (오른쪽을 늘렸는데 합이 줄어들 수도 있어서, “좁혀가기”가 보장되지 않음)