#7 투 포인터(Two Pointers)

 투 포인터 알고리즘은 일차원 배열상에서 두개의 포인터를 움직여 문제를 해결하는 방식을 말한다.  

일반적으로 두 개의 포인터는 각각 배열의 항목 중 하나를 가리키거나 연속구간의 시작과 끝을 나타내는 형태로 사용된다.

 

1. 연속구간의 합에 관한 문제

 합이 특정한 수가 되도록 하는 모든 연속 부분구간을 구하는 문제는 투 포인터 알고리즘이 사용되는 대표적 예시이다.  절차는 다음과 같다.

 

주어진 수열 seq 의 길이가 n 일 때, seq의 연속 부분수열 중 합이 m 이 되는 것의 갯수 answer 를 구한다면

① 주어진 수열의 시작과 끝을 나타낼 s, e(두 개의 포인터)와 구간의 합을 나타낼 t를 모두 0으로 초기화

② t에 seq[e] 를 더한다.

③ s가 e보다 커지거나 t가 m보다 작거나 같아질 때 까지 시작구간을 뒤로 이동하고 그만큼 합계를 감산

④ 연속구간의 길이가 1이 될때까지도 t가 m보다 크다면 e가 구간의 끝인 상태에선 더이상 t가 m이 될

    가능성이 없기 때문에 e += 1

⑤ ④에서 s<=e 인채로 t가 m보다 작거나 같아졌을 경우, t == m이라면 answer += 1

⑥ ②~⑤를 e가 n-1 이하일 동안 반복

⑦ 반복문이 종료된 후 answer 가 seq의 연속 부분수열 중 합이 m이 되는 것의 갯수가 된다.

 

아래는 이를 구현하여 문제(https://www.acmicpc.net/problem/2003)를 해결한 코드이다. 

import sys

input = sys.stdin.readline


def sol2003():
    n, m = map(int, input().split())
    seq = list(map(int, input().split()))
    
    # 1
    s, t = 0, 0
    res = 0
    
    # 6
    for e in range(n):
    	# 2
        t += seq[e]
        
        # 3
        while t > m and s <= e:
            t -= seq[s]
            s += 1
           
        # 4
        if s > e:
            continue
            
        # 5
        if t == m:
            res += 1
            
    # 7
    return res


if __name__ == '__main__':
	print(sol2003())

 

2. 두 수의 합

 정렬된 수열의 양끝에서 두 개의 포인터를 좁혀가면서 두 수의 합이 특정 값과 같은 경우의 수를 찾거나 

특정 값에 가장 가까운 쌍을 찾는 등의 문제 또한 투포인터를 사용하여 해결 가능하다.  합의 특정한 수가 되는 경우의 수를 구하는 것은 매우 간단하고 투포인터를 사용하는 것 보다 쉬운 해결책도 있기 때문에 여기서는 특정 수에 가장 가까운 쌍을 찾는 문제만을 다룬다.

 

길이가 N인 수열 seq가 주어졌을 때, 이 중 두 수를 합한 값이 M에 가장 가까운 순서쌍을 구한다면

① seq를 오름차순 정렬

② 시작과 끝 포인터 s, e를 각각 0, N-1 로 초기화

③ 답이 될 두 수 r1, r2를 각각 0으로, M과의 차의 최솟값 d를 무한으로 초기화 

④ seq[s] + seq[e]와 M의 차가 d보다 작은 경우 r1, r2를 seq[s], seq[e]로, d를 abs(M-(seq[s]+seq[e]))로 갱신

⑤ seq[s] + seq[e] 가 M보다 작다면 s += 1, 크다면 e -= 1, M과 같다면 더이상 탐색이 필요없기 때문에 반복 종료

⑥ ④, ⑤ 과정을 s <= e인 동안 반복한다.

 

아래는 이를 구현하여 문제(https://www.acmicpc.net/problem/2470)를 해결한 코드이다.

import sys

input = sys.stdin.read


def sol2470():
    n, *seq = map(int, input().split())
    # 1
    seq.sort()
    
    # 2
    s, e = 0, n-1
    
    # 3
    r1, r2, d = 0, 0, float('inf')
    
    # 6
    while s < e:
        t = seq[s]+seq[e]
        # 4
        if abs(t) < d:
            r1, r2, d = seq[s], seq[e], abs(t)
            
        # 5
        if t == 0:
            break
        elif t < 0:
            s += 1
        else:
            e -= 1
    return '%d %d' % (r1, r2)


if __name__ == '__main__':
    print(sol2470())

 

3. Meet in the Middle

 문제의 풀이법이 지수시간을 가질 때( ex) 2^N ) N이 조금만 커져도 해결에 엄청난 시간이 소모된다. 

Meet in the Middle은 이러한 문제를 절반으로 나누어 각각 해결하는것으로 시간복잡도를 줄이는 방식이다. 

 

N(1<=N<=40)개의 정수로 이루어진 수열 seq가 주어졌을 때 seq의 부분수열 중 크기가 양수이고 합이 S가 되는것의 수를 구할 경우, 단순히 모든 조합을 따진다면 2^40이라는 엄청난 시간이 필요하다. 이를 Meet in the middle 알고리즘을 활용하여 해결해본다.

① 주어진 수열을 반으로 나눈다

② 나누어진 각 수열에 대해 모든 부분 수열의 합을 구하여 dictionary에 카운트한다.(ls, rs)

③ 한쪽의 부분수열의 합이 T가 되는 경우의 수에 대해 다른 한쪽의 부분수열의 합이 S-T 가 되는 경우의 수를 곱하여 더해나간다. 

④ 만약 S가 0이라면 크기가 0인 부분수열(공집합)이 답에 포함되기 때문에 답에서 1을 빼준다.

 

아래는 이를 구현하여 부분수열의 합 문제(https://www.acmicpc.net/problem/1208)를 해결한 코드이다.

import sys
from itertools import combinations

input = sys.stdin.read


def sol1208():
    n, s, *seq = map(int, input().split())
    mid = n // 2
    # 1
    left, right = seq[:mid], seq[mid:]
    
    # 2
    ls, rs = {}, {}
    for c in [map(sum, combinations(left, i)) for i in range(mid + 1)]:
        for t in c:
            ls[t] = ls.get(t, 0) + 1
    for c in [map(sum, combinations(right, i)) for i in range(n - mid + 1)]:
        for t in c:
            rs[t] = rs.get(t, 0) + 1

    # 3
    res = 0
    for t in ls.keys():
        res += ls[t] * rs.get(s - t, 0)
        
    # 4
    if s == 0:
        res -= 1
        
    return res


if __name__ == '__main__':
    print(sol1208())

Meet in the middle 알고리즘은 큰 문제를 작은문제로 나누어 해결하는 부분에서 분할정복과 비슷한 느낌이지만 문제를 재귀적으로 쪼개나가며 해결하는 방식은 아니라는점에서 차이가 있다.