[알고리즘] 투 포인터 기법
투 포인터(two pointers) 기법이란 배열과 리스트 같은 선형(linear) 자료 구조에서 데이터를 순차적으로 탐색하는데 사용되는 방법 중 하나이다. 투 포인터 기법은 간단한 방법으로 알고리즘의 성능을 높이는데 주로 사용된다. 문제 해결 시 브루트 포스(brute-force) 방법의 시간 복잡도가 높은 경우 투 포인터를 사용해볼 수 있다.
투 포인터 기법에서 포인터(pointer)란 선형 자료 구조에서 데이터의 위치를 가리키는 것을 의미한다. 배열이나 리스트 자료 구조에서 포인터는 인덱스(index)를 참조한다. 투 포인터 기법은 두 개의 서로 다른 포인터를 사용하여 자료 구조를 탐색한다. 보통 두 포인터를 각각 양쪽 끝에서 시작하여 서로 반대 방향으로 이동시켜 서로 만나도록 포인터를 이동시키면서 원하는 문제의 답을 구한다.
문제에 따라 투 포인터 기법을 사용하기 위해 선형 자료 구조를 정렬해야 할 수도 있다. 예를 들어 배열에서 두 수의 합이 특정 값인 두 원소를 찾는 문제의 경우 두 포인터의 합이 목표 값보다 작다면 왼쪽 포인터를 오른쪽으로, 목표 값보다 크다면 오른쪽 포인터를 왼쪽으로 이동시켜야 하며 이러한 포인터 이동은 배열이 정렬되었음을 전제로 한다. 배열이 정렬되어 있어야 양쪽 포인터의 이동이 값을 증감시키기 때문이다. 윈소의 인덱스를 구하는 문제인 경우 정렬 시 인덱스가 변경되므로 투 포인터 기법을 사용할 수 없지만 원소의 값을 구하는 문제인 경우 투 포인터 기법을 사용할 수 있다.
Comments