🔁 투 포인터 – 이중 for문을 줄이는 알고리즘 기법

❓ 문제 설명

 

이중 for문(O(n^2))을 사용하는 로직은 느리고 비효율적
하지만 모든 경우를 비교해야 한다면 어떻게 해야 할까?
→ 투 포인터(투-포인터) 기법을 사용하면 대부분의 이중 반복을 O(n) 수준으로 최적화할 수 있음

---

📌 제한 조건

 

• 정렬된 배열 혹은 순서가 중요한 데이터

• 두 인덱스를 이동하며 전체 범위를 확인해야 하는 경우

• 누적합, 합 비교, 구간 탐색 문제 등

---

🔍 풀이 전략

 

✔︎ 두 개의 포인터를 사용해서 위치를 기억하며 이동

✔︎ 조건에 따라 하나만 이동하거나 둘 다 이동

✔︎ while문, 또는 단일 for문으로 구현 가능

✔︎ 포인터 변수명 예시 :

→ start, end 또는 left, right

→ s, e / l, r 등

✔︎ 화살표가 양방향으로 움직이는 그림이 있다면 → 투 포인터 가능성 높음

---

✅ 자주 쓰이는 상황

 

1️⃣ 특정 합을 만족하는 두 수 찾기

2️⃣ 부분 배열의 합이 특정 값 이상인 최소 길이 구하기

3️⃣ 회문 여부 검사 (양쪽 끝에서 좁혀오며 비교)

4️⃣ 슬라이딩 윈도우와 함께 사용하는 경우도 많음

---

💡 해설

 

이중 for문은 완전탐색에서는 유용하지만, 입력이 많을수록 성능 저하가 큼
투 포인터 기법은 "모든 경우를 확인하면서도, 불필요한 비교를 하지 않도록 포인터로 조절"함
👉 이중 반복을 줄일 수 있다는 것이 가장 큰 장점