투 포인터
투 포인터은 두 개의 인덱스를 이동시켜 원소 쌍 또는 연속 구간의 조건을 검사한다 배열 구간·탐색 기법 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수...
| 분류 | 알고리즘 · 배열 구간·탐색 기법 |
|---|---|
| 목적 | 두 개의 인덱스를 이동시켜 원소 쌍 또는 연속 구간의 조건을 검사한다 |
| 처리 방식 | 정렬된 배열에서는 두 끝에서 시작해 합의 크기에 따라 한쪽 포인터를 이동한다 |
| 복잡도·성능 | 두 포인터가 각각 한 방향으로 O(n)번 움직이면 시간 O(n), 추가 공간 O(1) 가능 |
| 필수 조건 | 포인터 이동이 답을 누락시키지 않는 정렬·단조성 조건이 필요하다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
투 포인터은 두 개의 인덱스를 이동시켜 원소 쌍 또는 연속 구간의 조건을 검사한다 배열 구간·탐색 기법 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 정렬된 배열에서는 두 끝에서 시작해 합의 크기에 따라 한쪽 포인터를 이동한다. 연속 구간 문제에서는 시작·끝 포인터를 단조롭게 움직여 각 원소를 중복 처리하지 않게 한다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 두 포인터가 각각 한 방향으로 O(n)번 움직이면 시간 O(n), 추가 공간 O(1) 가능 올바르게 적용하려면 포인터 이동이 답을 누락시키지 않는 정렬·단조성 조건이 필요하다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 두 수의 합·연속 구간·중복 제거 등에 사용하며 슬라이딩 윈도우와 겹치는 경우가 있지만 항상 동일한 기법은 아니다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]