[Algorithm] Two-Pointers(투 포인터)

---

투 포인터

배열이나 리스트를 탐색할 때, 두 개의 포인터를 사용하여 효율적으로 문제를 해결하는 알고리즘 기법이다. 주로 정렬된 배열에서 특정 조건을 만족하는 값을 찾거나, 구간 합을 계산하는 문제 등에 사용된다.

• 효율적 : 정렬된 배열에서 탐색 시 O(n) 으로 해결 가능
• 간단한 구현 : 포인터 이동만으로 문제 해결

 

투 포인터 개념

• 포인터(Pointer) : 배열의 특정 인덱스를 가리키는 변수
• 두 개의 포인터를 배열의 양 끝 또는 특정 시작점과 끝점에 두고, 포인터를 이동시키며 문제를 해결

 

사용 조건

• 배열이 정렬된 경우가 많을 때
• 특정 구간이나 두 값의 합을 계산할 때 효율적으로 탐색할 필요가 있을 때

 

대표적인 동작 방식

1. 시작과 끝 포인터 사용 (양 끝에서 이동)
   • 배열의 가장 왼쪽과 오른쪽 끝에 포인터를 둔 뒤, 조건에 따라 포인터를 좁혀나가며 문제 해결
   • 예 : 두 수의 합이 특정 값인지 확인
2. 슬라이딩 윈도우 (한쪽 방향으로 이동)
   • 두 포인터를 배열의 시작점에 두고, 한쪽 방향으로 확장하거나 축소하며 문제를 해결
   • 예 : 특정 길이의 구간에서 최대/최소 합을 구하는 문제

종료 조건

• start 가 end 보다 커질 때, 이미 탐색한 걸 다시 탐색하게 되므로 종료시킨다.

 

 

투 포인터를 사용할 수 있는 문제 유형

• 두 수의 합 (Two Sum)
• 특정 구간의 합 (Subarray Sum)
• 두 배열 비교
• 최적의 짝짓기 문제 (예: 구명보트 문제)

[프로그래머스 구명보트 문제] 👇

프로그래머스

 

[구명보트 문제 풀이 정리] 👇

[Programmers] L2. 구명보트 (Python/투 포인터)

 

---