[알고리즘] 투 포인터

투 포인터 (Two Pointers) 알고리즘이란?

• 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘
• 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻을 수 있음

쓰는 이유?

• 시간 복잡도 단축이 제일 크다.

보통 이중 for 문을 사용하여 구하는 데, 시간 복잡도가 O(N^2) 으로 Input 값이 커지면 상당히 커진다.

투 포인터를 사용하면 시간 복잡도가 O(N+M)으로 상당히 많이 단축 된다.

부분 합이 5인 연속된 수열의 수를 구해보자!

5
1 2 3 2 5
5

1. 이중 for 문

n = int(input())
arr = list(map(int, input().split()))
x = int(input())

ans = 0
for i in range(n):
    for j in range(i+1, n):
        if arr[i] + arr[j] == x:
            ans += 1

print(ans)        # 2

 

• 전체를 순회하면서 리스트의 두 번째부터 더해가며 부분 합을 구하는 방식
• 시간 복잡도 O(N^2) 이다

2. 투 포인터

n = int(input())
arr = list(map(int, input().split()))
x = int(input())

arr.sort()
start, end = 0, n - 1
ans = 0
while True:
    if start >= end:
        break
    temp = arr[start] + arr[end]
    if temp == x:
        start += 1
        ans += 1
    elif temp > x:
        end -= 1
    else:
        start += 1
print(ans)        # 2

 

• 일단 정렬하고 시작
• 포인터를 시작과 끝에 두면서 비교를 하기 때문에 시간 복잡도를 줄일 수 있음

STEP 0 (기본)

STEP 1 (정렬)

STEP 2 (확인 후 End 옮기기)

STEP 3 (확인 후 Start 옮기기)

STEP 4 (반복)

STEP 5 (동일 위치면 Break)

백준 참고 문제집

https://www.acmicpc.net/problemset?sort=ac_desc&algo=80

문제 - 1 페이지

 

❤ 본 포스팅에서 지적과 좋아요는 감사하게 받겠습니다.