[자료 구조/알고리즘] 투 포인터 기법
투 포인터(two pointers) 기법이란 배열과 리스트 같은 선형(linear) 자료 구조에서 데이터를 순차적으로 탐색하는데 사용되는 방법 중 하나이다. 투 포인터 기법은 간단한 방법으로 알고리즘의 성능을 높이는데 주로 사용된다. 문제 해결 시 브루트 포스(brute-force) 방법의 시간 복잡도가 높은 경우 투 포인터를 사용해볼 수 있다.
투 포인터 기법에서 포인터(pointer)란 선형 자료 구조에서 데이터의 위치를 가리키는 것을 의미한다. 배열이나 리스트 자료 구조에서 포인터는 인덱스(index)를 참조한다. 투 포인터 기법은 두 개의 서로 다른 포인터를 사용하여 자료 구조를 탐색한다. 보통 두 포인터를 각각 양쪽 끝에서 시작하여 서로 반대 방향으로 이동시켜 서로 만나도록 포인터를 이동시키면서 원하는 문제의 답을 구한다. 동일한 방향이지만 서로 다른 속도로 두 포인터를 이동하는 방법을 사용하기도 한다.
문제에 따라 투 포인터 기법을 사용하기 위해 선형 자료 구조를 정렬해야 할 수도 있다. 예를 들어 배열에서 두 수의 합이 특정 값인 두 원소를 찾는 문제의 경우 두 포인터의 합이 목표 값보다 작다면 왼쪽 포인터를 오른쪽으로, 목표 값보다 크다면 오른쪽 포인터를 왼쪽으로 이동시켜야 하며 이러한 포인터 이동은 배열이 정렬되었음을 전제로 한다. 배열이 정렬되어 있어야 양쪽 포인터의 이동이 값을 증감시키기 때문이다. 윈소의 인덱스를 구하는 문제인 경우 정렬 시 인덱스가 변경되므로 투 포인터 기법을 사용할 수 없지만 원소의 값을 구하는 문제인 경우 투 포인터 기법을 사용할 수 있다.
순환 탐지 알고리즘
순환 탐지(cycle detection) 알고리즘이란 연속적인 자료 구조에서 주기적인 반복 참조 구조인 순환(cycle)을 찾는 알고리즘이다. 예를 들어, 연결 리스트에서 마지막 노드가 첫 번째 노드를 참조하는 경우 해당 연결 리스트는 순환 구조를 가지고 있다. 대표적인 순환 탐지 알고리즘으로는 거북이와 토끼 알고리즘(tortoise and hare algorithm)으로 불리는 플로이드 알고리즘(Floyd’s algorithm), 브렌트 알고리즘(Brent’s algorithm) 등이 있다.
플로이드 알고리즘은 두 개의 포인터가 동일한 위치에서 이동을 시작하지만 서로 다른 속도로 이동(하나의 포인터는 한 번에 1씩, 다른 포인터는 2씩 이동)한다. 사이클이 존재한다면 두 포인터는 어느 시점에 만나게 되며 사이클이 없다면 두 포인터는 각각 양쪽 끝에 도달한다.
플로이드 알고리즘을 통해 다음 방법으로 사이클의 시작 지점을 확인할 수 있다.
슬라이딩 윈도우 기법
슬라이딩 윈도우(sliding window) 기법이란 고정된 크기의 데이터를 포함하는 윈도우(window)를 사용하여 이를 이동시키면서 전체 데이터를 탐색하여 문제를 해결하는 방법이다.
투 포인터와 슬라이딩 윈도우 기법 모두 두 개의 포인터를 이동시키면서 문제를 해결하는 것은 동일하지만 투 포인터 기법은 두 개의 포인터 사이에 존재하는 데이터의 크기를 일정하게 유지하지 않는 반면 슬라이딩 윈도우 기법은 데이터의 크기가 일정하도록 두 포인터를 이동시킨다.
Comments