투포인터 알고리즘(Two Pointers Algorithm)

이번에 배워볼 알고리즘은 투포인터 알고리즘이다. 요즘 코딩 테스트에서 투포인터 알고리즘이 자주 나와서 한번 짚고 넘어가려고 한다.

C언어를 배웠다면 포인터라는 개념은 어느 정도 알고 있을 것이다. 투포인터 알고리즘은 C언어의 포인터는 아니지만 비슷한 개념으로 어떤 위치?를 가리키는 2개의 포인터를 적절히 활용하여 원하는 값을 얻어내는 방법이다.

​투포인터 알고리즘 또한 알고리즘이기보단 기법에 가깝기 때문에 예시를 통해 직접 겪어보는 것이 좋다.

​

투포인터 알고리즘을 이해하기 위한 대표적인 예시로 부분합이라는 문제가 있다. 우리도 이 문제를 통해 투포인터 알고리즘을 이해해 보자.

​부분합이라는 문제는 리스트에 1부터 N까지 수열이 주어지면 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 길이를 구하는 문제이다. 예를 들어 다음과 같은 문제가 있다고 하자.

 

{ 5, 1, 3, 5, 10, 7, 4, 9, 2, 8 } 총 10개의 정수로 이루어진 리스트에서 연속된 수들의 부분합 중에 그 합이 15 이상이 되는 최소 길이를 구해보자.

 

만약 최소 1자리부터 최대 10자리까지 모든 부분합 수열을 구한다면 부분합 수열의 총개수는 N * (N + 1) / 2이다. 이는 O(N^2)의 시간 복잡도를 가지며 N이 굉장히 크다면 상당히 부담스러울 것이다. 좀 더 빠른 시간 내에 문제를 해결할 수는 없을까?

우리는 투포인터를 사용하여 O(N)의 시간 만에 정답을 구할 수 있다. 부분합은 결국 연속된 수들의 합을 의미한다. 그렇다면 현재 연속된 수열의 합이 15를 넘게 된다면 어떻게 될까? 이미 15를 넘기 때문에 그 뒤의 정수들은 더할 의미가 없어진다. 부분합이 15보다 커질 수도 있고 작아질 수도 있지만 결국 현재 부분합 수열의 길이보다 1만큼 증가하기 때문에 최소 길이가 성립될 수 없기 때문이다.

그렇다면 어떻게 해야 할까? 현재 부분합에서 제일 왼쪽 수를 빼고 없애주면 된다. 그렇게 한다면 현재 수열의 값은 15보다 작아지게 될 것이고 우측으로 나아갈 수 있을 것이다.

이 과정을 현재의 부분합이 15보다 작은데 수열의 우측이 리스트의 마지막을 가리킬 때까지 반복하면 된다. 그 이유는 우측이 리스트의 마지막을 가리킨다는 것은 더 이상 더할 정수가 존재하지 않기 때문에 더 이상 15를 넘을 수 없게 된다.

만약 현재의 부분합 수열에서 제일 왼쪽과 우측을 알고 있다면 이를 빠르게 수행할 수 있을 것이다. 이를 우리는 2개의 포인터라는 변수로 가리키도록 할 것이다. 이게 바로 투포인터 알고리즘이다.

​

글로만 보면 무슨 소리인지 이해가 안 갈 수도 있을 것이다. 그림으로 투포인터의 동작 과정을 이해해 보자.

 

투포인터 알고리즘을 이용하여 O(N)이라는 시간 만에 2라는 최소 길이를 구하였다.

 

위의 문제를 모든 부분합을 구하는 방법 & 투포인터 알고리즘을 사용한 방법을 Java로 구현한 코드는 다음과 같다.

public class Blog {

	static int[] list = {5, 1, 3, 5, 10, 7, 4, 9, 2, 8};
	static int all_Set_Cnt, two_Point_Cnt;

	public static void main(String[] args) {
		System.out.println(all_Set());
		System.out.println(two_Pointer());
		System.out.println(all_Set_Cnt + " vs " + two_Point_Cnt);
	}

	public static int all_Set() {
		int minLen = (int)1e9;

		for (int i = 0; i < list.length; ++i) {
			int sum = 0;
			for (int j = i; j < list.length; ++j) {
				all_Set_Cnt++;

				if (sum >= 15) {
					minLen = Math.min(minLen, j - i);
				}

				sum += list[j];
			}
		}

		return minLen;
	}

	public static int two_Pointer() {
		int left = 0, right = 0;
		int sum = 0, minLen = (int)1e9;

		while (true) {
			two_Point_Cnt++;

			if (sum >= 15) {
				minLen = Math.min(minLen, right - left);
				sum -= list[left++];
			} else if (right == list.length) {
				break;
			} else {
				sum += list[right++];
			}
		}

		return minLen;
	}
}

결과를 보면 투포인터 알고리즘을 이용하는 것이 모든 부분합 수열을 구하는 것보다 훨씬 빠른 것을 알 수 있다.