투포인터 알고리즘

froajnzd·2024년 1월 18일

algorithm

목록 보기

4/11

Two pointer
리스트에 순차적으로 접근해야 할 때 두 개의 점 위치를 기록하는 알고리즘
이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터(변수) 움직임으로 O(N)에 해결하는 알고리즘

두개의 포인터를 어디에 설정하는 지가 문제의 관권

합병정렬(merge sort)의 counquer 영역의 기초가 되기도 함

📕 Two pointer를 사용해야하는 문제의 조건

투포인터로 이분탐색 문제를 해결할 수 있다.

💡 Two pointer의 장점

완전탐색으로 해결하는 것보다 시간복잡도를 줄일 수 있다.

📝 Two pointer를 사용하는 문제의 예

주어진 리스트를 변형 없이 그대로 순차적으로 사용해야 하는 문제
주어진 리스트의 조건을 만족하는 특정 구간을 찾아야 하는 문제
리스트의 원소 중 음수가 없을 때(모두 같은 부호여야 함)

🎁 Two pointer를 사용하는 방법

두 개의 포인터를 순차적으로 맨 앞 두 개를 사용할 수 있고,
맨 앞과 맨 뒤를 포인터로 사용하여 문제를 푸는 경우도 있다.

c.f. 슬라이딩 윈도우

투포인터처럼 구간을 훑으며 지나가는데 공통점이 있지만, 슬라이딩 윈도우는 매 순간 구간의 넓이가 동일하다는 차이점이 있다.

슬라이딩 윈도우는 구간의 크기가 같기 때문에 구해야할 전체 길이가 주어져 있을 때 반복 횟수를 고정할 수 있다는 장점이 있다. (for 문으로 구할 수 있음)

c.f. 이진탐색

투포인터 알고리즘은 포인터를 두 개로 지정하여 알고리즘을 진행하지만,

이진탐색 알고리즘은 포인터를 세 개를 사용하여(start, mid, end) mid값과 기준 값을 비교하여 범위를 줄여가며 진행한다.

🏃‍ 예시 문제 1

<BAEKJOON: 실버 4> 주몽

해답

정렬 후 양 끝을 포인터로 잡아서 양 포인터의 값을 합한 값이 M과 같다면 카운팅한다.

import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
materials = list(map(int, input().split()))

materials.sort()

st, end = 0, N-1
result = 0
while(st < end):
    mat = materials[st] + materials[end]
    if M == mat:
        result += 1
        st, end = st+1, end-1
    elif M > mat:
        st+=1
    else:
        end -= 1

print(result)

🏃‍ 예시 문제 2

<BAEKJOON: 실버 3> 게으른 백곰

해답

이번 문제는 두 개의 포인터를 맨 앞 두개로 두고 풀어보았다.

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
locIce = []
for i in range(N):
    a, b = map(int, input().split())
    locIce.append([b,a])
locIce.sort()

l, r = 0, 0
sum = locIce[0][1]
maxsum = locIce[0][1]
while (l <= r and r < N):
    if (locIce[r][0] - locIce[l][0] <= 2*K):
        maxsum = max(maxsum, sum)

    if (locIce[r][0] - locIce[l][0] < 2*K):
        # right update
        r += 1
        if r == N:
            break
        sum += locIce[r][1]
    else: # left update
        sum -= locIce[l][1]
        l += 1

print(maxsum)

🏃‍ 예시 문제 3

<BAEKJOON: 실버 3> 좋다

해답

a+b=c에서 a, b, c가 모두 달라야함을 명심한다.

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))

good = 0
a.sort()
for i in range(N):
    st, end = 0, N-1
    while (st < end):
        if a[st] + a[end] == a[i]:
            if i != st and i != end:
                good += 1
                break
            elif i == st:
                st += 1
            elif i == end:
                end -= 1
        elif a[st] + a[end] > a[i]:
            end -= 1
        else:
            st += 1
print(good)