투 포인터

투 포인터

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어있는 두 리스트의 합집합에도 사용된다.

시간 복잡도

투 포인터는 O(n)의 시간 복잡도를 가집니다.

 

1. sum에 누적을 시키면서 전체를 탐색하는 투 포인터 이동 원칙

투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우의 수를 구한다.

start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 효과가 같으며, end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장한다는 의미이다. 같을 때는 1 증가시키고 end_index를 오른쪽으로 이동한다.

 

while(end_index != N) 일 때까지 반복

• sum > N : sum = sum - start_index; start_index++;
• sum < N : end_index++; sum = sum sum + end_index;
• sum == N : end_index++; sum = sum + end_index; count++;

2. 2개를 가지고 전체를 탐색하는 투 포인터 이동 원칙

오름차순으로 정렬해야된다. 

while( i < j )

• A[i] + A[j] > M : j--;   -> 번호의 합이 M보다 크므로 큰 번호 index를 내린다.
• A[i] + A[j] < M : i++;  -> 번호의 합이 M보다 작으므로 작은 번호 index를 올린다.
• A[i] + A[j] == M : i++; j--; count++;  -> 양쪽 포인터를 모두 이동시키고 count를 증가시킨다.