투 포인터 알고리즘

투포인터(Two Pointers) 알고리즘

투포인터 알고리즘은 정렬된 배열이나 리스트에서 두 개의 포인터(인덱스)를 사용하여 문제를 해결하는 기법.

개념

• 배열이나 리스트에서 두 개의 포인터 변수를 사용하여 특정 조건을 만족하는 값들을 탐색한다.
• 일반적으로 두 포인터를 서로 다른 방향에서 움직이며 탐색한다.

대표사례

• 합이 특정 값이 되는 두 수 찾기: 배열에서 두개의 숫자 합이 M이 되는 경우 찾기
• 두 개의 리스트에서 공통 원소 찾기: 정렬된 두 개의 리스트에서 교집합 찾기
• 배열의 연속된 부분 구간 찾기: 특정 합을 갖는 연속된 부분 배열 찾기 (슬라이딩 윈도우 기법)
• 정렬된 배열에서 특정 조건을 만족하는 개수 세기: 정렬된 배열에서 차이가 K인 숫자 쌍의 개수 찾기