[알고리즘] 투 포인터

 

 

 

개인 공부 후 자료를 남겨놓기 위한 목적이므로,
생략되거나 오류가 있을 수 있음을 알립니다.

 

 

 

 

 

투포인터

---

 

1. 투포인터란?

 

투포인터 알고리즘(Two Pointer Algorithm) 또는 슬라이딩 윈도우(Sliding Window) 라고 부른다.

 

간단한 원리로는 1차원 배열이 존재할 때,

 

이 배열에서 각자 다른 원소를 가리키고 있는 2개의 '포인터'를 조작하면서 원하는 값을 얻는 알고리즘이다.

 

---

 

2. 기본 메커니즘

 

보통 투포인터에서는 두개의 포인터를 strat(s), end(e)로 설정하고,

 

우리가 문제를 풀거나, 알고리즘을 짜면서 만든 특정한 조건에 따라 각 포인터를 한칸씩 이동시켜

 

바라보는 배열의 크기를 조절한다.

 

이렇게 특정 구간의 배열만 바라보면서 해답을 찾아내는 알고리즘이다.

 

 

1. s = 0, e = 0인 경우

 

해당 포인터들을 s = 0, e = 0로 두거나 s = 0, e = "마지막 인덱스" 로 두고 사용한다.

 

첫번째 조건인 s = 0, e = 0 인 상황을 그림을 이용하여 이해하여 보자.

 

 

 

처음에는 두 포인터 다 0인 상황에서 출발하며,

 

우리가 설정한 조건에 따라 s 또는 e포인터가 뒤로 한칸씩 이동하게 된다.

 

이때 절대 s는 e보다 커져서는 안된다. ( s <= e )

 

코드가 진행됨에 따라 포인터가 이동하게 되고,

 

 

포인터가 가리키는 범위에 따라 우리는 해당 구간만 확인하게 된다.

 

이렇게 특정 구간만 확인할 수 있게 되므로 슬라이딩 윈도우라고도 부른다.

 

 

2. s = 0, e ="마지막 인덱스인 경우"

 

포인터가 가리키는 배열의 크기가 처음부터 배열 전체를 의미하기 때문에

 

경우에 따라 좀 더 빠른 속도로 우리가 원하는 해를 구할 수 있다.

 

 

 

---

3. 코드를 통한 이해

 

1. s = 0, e = 0인 경우

 

수들의 합 2 문제를 통해 알아보도록 하자.

 

이 문제의 경우에는 특정 구간의 합이 문제에서 주어지는 M이 되는 경우의 수를 구해야 한다.

 

따라서 포인터 s, e를 모두 0으로 두고 이 포인터를 이동시키면서 구간의 합이 M이 되는 값을 구하면 된다.

 

해당 코드의 주석을 통해 이해하기 쉽도록 설명을 해보았다.

 

 

2. s = 0, e = "마지막 인덱스" 인 경우

이번에는 두 수의 합 문제를 이용하여 위 경우를 이해해보도록 하자.

 

이 문제를 처음 보았을 때는 어떻게 진행해야 할지 감이 잘 안올 수도 있는데,

 

주어지는 배열의 순서가 중요하지 않는 경우, 기본적으로 주어지는 배열을 정렬을 하면

 

훨씬 보기 편해진다.

 

예제를 정렬을 해보게 되면.

 

5 12 7 10 9 1 2 3 11 => 1 2 3 5 7 9 10 11 12 로 바뀌게 되고,

 

이때 s = 0, e = "마지막 인덱스" 로 두고, 두 포인터의 합을 구한 뒤, 정렬이 되있기 때문에

 

합이 문제에서 주어지는 x보다 작은 경우 s를 오른쪽으로 이동시키고, 큰 경우 e를 왼쪽으로 이동시키면 된다.

 

그렇게 두 포인터를 이동시키다가 s와 e가 교차하는 순간 코드를 마무리 지으면,

 

x가 될 수 있는 모든 경우를 체크했으므로 정답이 나오게 된다.

 

코드로 확인해보자.