투 포인터

투 포인터는 직관적이면서도 강력한 알고리즘 도구이다. 쓰는 방법은 사실 단순하다. 보통 리스트를 돌 때 기본적으로 하나의 포인터만을 가지고 리스트를 탐색한다. 의식적으로 포인터를 쓰지 않더라도 사실 우린 은연 중에 포인터의 원리를 이용하여 탐색하며 대게는 하나의 포인터만을 이용하여 하나씩 차례차례 탐색한다. 기본적인 접근 방법은 하나의 포인터를 이용하는 것이 옳다. 탐색 문제라고 해서 모두 투 포인터를 적용하는 것이 올바른 접근 방법이다. 그렇다면 어떤 문제에 투 포인터를 적용할 수 있을까?

하나의 인덱스를 탐색할 땐 하나의 포인터를 이용해야 한다. 하지만 동시에 두 개의 인덱스를 탐색하고 싶다면 어떻게 해야할까? 다시 말해 시작과 끝이 존재하는 '범위'를 탐색할 때 하나의 포인터로 충분할까? 검지손가락 하나를 이용해 1m를 정의해보자. 우리는 우선 1m의 시작이 되는 점을 손가락으로 짚고 선언한다. "여기부터" 그리고 대략 1m가 되는 지점으로 손을 움직여 다시 선언한다. "여기까지" 하나의 손가락으로 1m를 정의하기 위해선 '시작 지점 선언'과 '종료 지점 선언' 총 두 번의 동작을 수행해야 한다.

이번엔 두 손가락을 이용해 1m를 정의해보자. 이 땐 왼손과 오른손을 동시에 움직여 두 손가락의 거리가 대략 1m가 됐을 때 손을 멈추고는 두 손가락 사이의 거리가 1m라고 말한다. 두 손가락을 이용하면 한 번의 동작으로 1m를 정의할 수 있다. 알고리즘의 투 포인터도 똑같은 효과를 보여준다. 단순히 두 개의 포인터를 동시에 이용할 뿐이지만 범위의 시작과 끝을 명시할 수 있다. 즉 투 포인터는 '범위'를 탐색할 때 시간 복잡도를 획기적으로 줄여주는 알고리즘이다. 범위를 탐색한다는 개념만 확실하게 잡혀있다면 투 포인터의 응용 문제는 모두 같은 원리를 적용하여 해결할 수 있다.

03-3 투 포인터

알고리즘이 매우 간단하므로 바로 실전 문제를 풀어보자.

---

문제 008 '좋은 수' 구하기

문제
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력
좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력 1
10
1 2 3 4 5 6 7 8 9 10

예제 출력 1
8

---

투 포인터는 범위 탐색에 쓰이지만 008 문제처럼 두 수의 합을 구할 때도 쓰일 수 있다. 시간 복잡도를 생각해보자. N의 개수가 최대 2000이라 해도 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 한다. 하지만 하나의 포인터만을 이용하면 최종 시간 복잡도는 N^3이 되어 제한 시간 내에 문제를 풀 수 없다. 따라서 좋은 수 하나를 찾은 알고리즘의 시간 복잡도는 최소 O(nlogn)이어야 한다. 정렬, 투 포인터를 사용하면 O(nlogn)으로 좋은 수 하나를 찾을 수 있다.(정렬의 시간 복잡도가 O(nlogn))

이 문제를 풀 때 한 가지 더 주의할 점은 주어진 수가 음의 정수가 될 수 있다는 것이다. 처음 문제 풀이를 할 때 조건을 꼼꼼히 읽지 않은 바람에 양의 정수만 A_i값으로 주어지는 줄 알고 엄한데서 또 삽질을 했다. 문제의 조건을 정확히 읽는 것은 올바른 방향으로 문제를 풀기 위한 첫걸음이란 것을 잊지 말자...!

n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = 0
for i in range(n):   # 음의 정수가 있는 경우라면 첫 번째 값도 다른 두 수의 합이 될 수 있다.
    p1 = 0
    p2 = n-1
    while p1 < p2:
        sum = a[p1] + a[p2]
        if sum == a[i]:
            if p1 != i and p2 != i:
                cnt += 1
                break
            elif p1 == i:
                p1 += 1
            elif p2 == i:
                p2 -= 1
        elif sum > a[i]:
            p2 -= 1
        else:
            p1 += 1
print(cnt)

03-4 슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음, 범위(window)를 유지한 채로 이동하며 문제를 해결한다. 투 포인터 알고리즘과 매우 비슷하고 원리도 간단하므로 바로 실전 문제로 넘어가 개념과 원리를 공부해 보자.