[알고리즘 시리즈] 투 포인터 : Two Pointer

---

투 포인터 : Two Pointer

목차

1. 투 포인터의 목적

2. 투 포인터의 적용 조건 및 적용 상황

3. 투 포인터의 사용법

4. Meet in the middle

---

1. 투 포인터의 목적

특정 조건에 따라 두 포인터를 조작하여 O(n) 만에 특정한 값을 찾는다.

 

2. 투 포인터의 적용 조건 및 적용 상황

1) 검색을 위해 사용한다.

특정한 조건을 만족하는 순서쌍을 찾는 문제에서 사용되는 투 포인터가 이 경우이다.

리스트가 오름차순 또는 내림차순으로 정렬되어 있어야 한다.

 

2) 한 배열을 정렬하기 위해 사용한다.

quick sort 정렬 연산 시 사용되는 투 포인터가 이 경우이다.

특별한 조건이 필요하지 않다.

 

3) 두 배열을 비교할 때 사용한다.

merge sort의 병합 단계가 이 경우이다.

두 배열이 오름차순 또는 내림차순으로 정렬되어 있어야 한다.

728x90

3. 투 포인터의 사용법

1) 양 쪽에서 두 포인터를 움직인다.

주로 정렬된 배열에서 특정 조건으로 수렴하도록 순서쌍을 찾는 경우 사용된다.

 

다음은 a + b = x 가 되는 순서쌍의 개수를 찾는 코드이다.

arr.sort()

cnt = 0
s, e = 0, n-1
while s<e:
    if arr[s]+arr[e] > x:
        e -= 1
    elif arr[s]+arr[e] < x:
        s += 1
    else:
        cnt += 1
        s += 1
print(cnt)

 

양 쪽에 두 포인터를 배치하고 x보다 크면 왼쪽 포인터를 오른쪽으로, x보다 작으면 오른쪽 포인터를 왼쪽으로 이동시킨다.

 

2) 한 쪽에서 두 포인터를 움직인다.

주로 누적합과 연결되며 연속된 수열을 찾는 경우 사용된다.

 

다음은 연속된 수들의 부분합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 코드이다.

arr = [0]+list(map(int, input().split()))
for i in range(1, N+1):
    arr[i] = arr[i]+arr[i-1]

s, e = 0, 1
min_len = float('inf')
while e <= N:
    if arr[e]-arr[s] >= S:
        min_len = min(min_len, e-s)
        s+=1
    else:
        e+=1
print(min_len if min_len != float('inf') else 0)

두 포인터 모두 왼쪽에 배치하고 부분 합이 S 이상 될 때까지 오른쪽 포인터를 증가시킨다. 부분 합이 S 이상 되면 왼쪽 포인터를 증가시키고 이 행위를 배열의 끝에 도달할 때까지 반복하여 최소 길이를 찾는다.

 

4. 부분합의 응용

Meet in the middle이 있다.

---