[Algorithm] Two Pointers

📌 Two Pointers

1차원 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 알고리즘

"특정한 합을 가지는 부분 연속 수열" 문제에서는
Two Pointer를 사용!

 

 

대표적으로 투 포인터를 활용한 문제는 다음과 같은 문제다.

Q. 정렬된 리스트 A와 타겟 값 S가 주어졌을 때, 두 수의 합이 S가 되는 순서쌍을 모두 구하여라.

 

가장 먼저 떠오르는 풀이는 이중 반복문을 이용해 탐색하는 방법일 것이다.

for i in range(len(A)):
    for j in range(i+1, len(A)):
        if A[i] + A[j] == S:
            print(A[i],A[j])

매우 단순하고 직관적이지만 시간 복잡도가 O(n^2)이라 데이터가 커지면 시간초과가 발생할 가능성이 크다.

또한 문제가 두 수의 합이 아니라 여러 수의 합일 경우, 다중 반복문을 사용하기 어렵다.

 

이럴 경우, 투 포인터를 사용하여 시간을 개선할 수 있다.

🔨 동작 원리

리스트를 오름차순으로 정렬한다.

start, end는 배열의 시작과 끝을 나타내는 포인터로, start, end = 0, 0으로 시작하며 항상 start <= end을 만족한다.

• 현재 부분합 < 원하는 결과 값
  • end를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 증가

• 현재 부분합 > 원하는 결과 값
  • start를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 감소

• 현재 부분합 == 원하는 결과 값
  • count+=1

📋 구현 코드

A.sort()

start = 0
end = len(A) - 1

while start <= end:
    tmp = A[start] + A[end]
    if tmp > S:
        start-=1
    elif tmp < S:
        end+=1
    else:
        print(A[start], A[end])
        start-=1
        end+=1

⏰ 시간 복잡도

Two Pointers 알고리즘의 시간복잡도는 O(n)

[참고]

https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0

https://velog.io/@adorno10/%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-Two-Pointer