[Algorithm] 투 포인터

Algorithm in HelloMinchan

[Algorithm] 투 포인터

(글쓴날 : 2020.05.13)

 

---

* 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다.

---

 

 

투 포인터

---

1) 투 포인터란?

투 포인터 알고리즘이란 주로 배열 안에 있는 값들을 연속해서 더하거나 연산하는 경우에 사용되며, 인덱스를 가리키는 두 개의 변수(포인터)를 선언하여 사용하는 특징이 있어 투 포인터라 불립니다.

예를 들어 N개의 숫자가 들어있는 배열이 주어질 때, 부분 집합의 합이 특정 숫자인 M인 경우의 수를 구하는 문제에 적용한다면, 배열의 인덱스를 가리키는 startPointer와 endPointer를 생성한 후 특정 규칙에 의해 각 포인터를 움직여 배열을 탐색해 문제를 해결할 수 있으며, 그 규칙은 다음과 같습니다.

 

1-1) 현재까지의 합이 M보다 크거나 같은 경우 합에서 endPoiner가 가리키고 있는 값을 뺀 후 endPointer를 +1 증가시킵니다.

1-2) 만약 startPointer의 값이 배열의 길이와 같을 경우 탐색을 종료합니다.

1-3) 나머지 경우(현재까지의 합이 M보다 작을 경우)에는 합에 startPointer가 가리키고 있는 값을 더한 후 startPointer를 +1 증가시킵니다.

 

2) 위의 세 규칙 중 해당하는 연산이 끝난 후 만약 현재까지의 합이 M과 같다면 답을 +1증가 시킵니다.

 

그렇다면, 왜 투 포인터를 사용할까요?

만약, 위와 동일한 문제를 완전 탐색을 적용하여 해결할 시 N만큼 반복문 2번을 돌리게 되므로 O(n²)의 시간 복잡도가 걸리게 됩니다.

하지만, 투 포인터를 사용한다면 한 번 답이 될 수 없다고 판명된 이후의 값들을 더 이상 탐색하지 않으므로(어차피 답이 될 수 없기 때문에) 시간 복잡도가 O(n)이 되어 완전 탐색에 비해 효율이 훨씬 좋아집니다.

따라서, 시간제한이 넉넉하지 않아 완전 탐색을 적용하여 해결하지 못하는 문제일 경우, 투 포인터를 적용하여 해결할 수 있습니다.

 

다만, 이 경우엔 배열의 원소가 자연수여야 하는 제약조건이 따르게 되므로 투 포인터를 사용하실 땐 꼭 문제의 조건을 확인하여 알맞은 상황에만 사용해야 하며, 포인터를 움직이는 규칙 또한 문제에 맞추어 변형해 주셔야 합니다.

---

2) 코드

코드는 위에서 예시로 든 문제를 해결하는 템플릿이며, 백준 2003번 수들의 합 2 문제와도 같습니다.

 

* Python 코드

N, M = 7, 5
arr = [1, 2, 3, 7, 5, 4, 3]
 
# 시작 포인터
startPointer = 0
# 끝 포인터
endPointer = 0
# 현재까지의 합
tot = 0
# 현재까지의 합이 M인 경우의 수
ans = 0
 
while(True):
    # 규칙 1-1)
    if tot >= M:
        tot -= arr[endPointer]
        endPointer += 1
    # 규칙 1-2)
    elif startPointer == len(arr):
        break
    # 규칙 1-3)
    else:
        tot += arr[startPointer ]
        startPointer += 1
    
    # 규칙 2)
    if tot == M:
        ans += 1
 
print(ans)  # 출력결과 : 2

---