728x90
반응형
1. 투 포인터(Two Pointers)란?
말 그대로 두 개의 포인터(인덱스)를 사용하여 배열이나 리스트를 효과적으로 탐색하는 기법이다.
- O(N)의 시간 복잡도를 가짐
2. 주요 유형
2.1. 시작점과 끝점에서 만나는 방식(양끝 조합)
주로 정렬된 배열에서 두 수의 합이 특정 K와 일치하는지 찾을 때 사용된다.
- Pointer 1 (Left): 배열의 시작점에서 오른쪽으로 이동한다.
- Pointer 2 (Right): 배열의 시작점에서 왼쪽으로 이동한다.
- 동작: 포인터에 위치한 두 요소의 합이 K보다 작으면 Left++, 크면 Right-- 를 수행하며 포인터를 이동한다.
2.2. 같은 방향으로 진행하는 방식(슬라이딩 윈도우)
연속된 부분 수열의 합이 특정 값 K를 만족하는지 찾을 때 사용된다. 배열의 정렬이 필요하지 않다.
- Start: 부분 구간의 시작
- End: 부분 구간의 끝
- 동작: 구간의 합이 타겟 K 보다 작으면 End를 키워 구간을 늘리고, 타겟 K 보다 크면 Start를 키워 구간을 줄인다.
3. 사용 시나리오
| 상황 | 해결 방법 |
| 배열에서 두 수의 합 찾기 | 1. 배열 정렬 2. 양 끝에서 포인터를 좁혀가며 탐색한다. |
| 특정 합을 가지는 부분 연속 수열 찾기 | start, end를 인덱스 0에서 시작하여 조건에 따라 늘리고 줄이며 배열 끝까지 탐색한다. |
| 정렬된 두 배열 합치기 | 각 배열의 시작점에 포인터를 두고 작은 값을 먼저 결과에 담는다. |
4. 알고리즘 설계 팁
- 포인터의 초기 위치: (0, 0)에서 시작할 것인지, 아니면 (0, N-1)에서 시작할 것인지
- 포인터 이동 조건: 어떤 상황에서 왼쪽 혹은 오른쪽 포인터를 움직일 것인지
- 반복 종료 조건: 두 포인터가 겹치면 끝낼 것인지, 배열의 끝에 도달하면 끝낼 것인지
- 주의: 투 포인터를 적용하기 전에 배열이 정렬되어야하는지 확인한다. 합을 찾는 문제에는 정렬이 필수일 경우가 많다.
728x90
반응형
'Coding Test > 알고리즘' 카테고리의 다른 글
| 백트래킹(Back Tracking) (0) | 2026.02.17 |
|---|---|
| 브루트 포스(Brute Force, 완전 탐색 기법) (0) | 2026.02.17 |
| 그래프 탐색 (Graph Search): 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) (0) | 2026.02.11 |
| 탐색 (Search) - DFS / BFS (0) | 2026.02.10 |
| 알고리즘 - 이분 탐색(Binary Search) (0) | 2026.02.03 |