투 포인터란?

• 포인터(pointer)는 일반적으로 변수의 메모리 공간 주소를 가리키는 변수이다.
• 문자열,리스트 등에서 포인터는 각 요소의 위치를 가리키는 변수라고 이해할 수 있다.
• 투 포인터(Two Pointers)는 두 개의 포인터를 활용해 문자열, 리스트 등의 요소를 효과적으로 탐색하는 기술이다.

예제

다음과 같은 수열이 주어졌을 때, 이 수열의 i번째 수부터 j번째 수까지의 합이 5가 되는 경우의 수를 구하는 프로그램을 작성하라.

반복문 풀이

• 이중 반복문으로 순회하여 합이 5가 되는 경우의 수를 셀 수 있다.
• 수열의 크기가 커질수록 수행 시간이 늘어난다.

투 포인터 풀이

투 포인터는 크게 두 가지 방식으로 쓰인다.

1. 양 끝에서 출발한 포인터가 중간에서 만나는 방식

2. 빠른 포인터(fast runner)가 느린 포인터(slow runner)를 앞서는 형식

두 번째 형식을 이용해 예제를 풀어보자.

• i와 j 두 개의 포인터를 만든다.
• 여기서 i는 느린 포인터, j는 빠른 포인터로 사용할 것이다.

• j를 먼저 이동시켰다.
• i와 j 사이에 수열의 합이 1 + 2 = 3 이므로 찾고자 하는 조건(수열의 합 : 5)에 부합하지 않는다. 따라서 j를 이동시킨다.

• i와 j 사이에 수열의 합이 1 + 2 + 3 = 6 이므로 찾고자 하는 조건(수열의 합 : 5)에 부합하지 않는다. 수열의 합 6이 조건 5보다 크므로, 이번에는 i를 이동시킨다.

• i와 j 사이에 수열의 합이 2 + 3 = 5 이므로 찾고자 하는 조건에 부합한다. 하나의 경우를 찾았다.

• i와 j 사이에 수열의 합이 2 + 3 + 4 = 8 이므로 찾고자 하는 조건(수열의 합 : 5)에 부합하지 않는다. 수열의 합 8이 조건 5보다 크므로, 이번에는 i를 이동시킨다.

• 이러한 방식으로 수열을 탐색하면 이중 반복문을 사용했을 경우보다 더 작은 시간복잡도로 정답을 찾아낼 수 있다.
• 이 문제에서 투 포인터를 활용하면 시간 복잡도는 O(n)이다.

참고자료

https://benn.tistory.com/9
https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0
https://butter-shower.tistory.com/226