파이썬 알고리즘 공부 - 투 포인터 / 백준 1940 / 백준 2018 / 백준 1253

투 포인터 알고리즘 (Two Pointer Algorithm)은

리스트에서 두 개의 포인터를 사용해 원하는 결과를 찾거나

특정 조건을 만족시키는 알고리즘이다.

보통 O(N)에 문제를 해결할 수 있어 유용하다!

 

 

두 포인터를 한 방향으로 진행: 두 포인터를 리스트의 시작 위치에서 같은 방향으로 움직인다.

일반적으로 시작 위치와 끝 위치에서 시작하고, 필요에 따라 포인터를 이동시키면서 조건을 만족하는 부분을 찾는다.

두 포인터를 반대 방향으로 진행: 두 포인터를 배열이나 리스트의 양 끝에서 서로 반대 방향으로 움직인다.

이 방식은 주로 두 요소의 합, 차 등을 비교하거나 반대 방향에서 수렴해가는 문제를 해결할 때 사용됩니다.

 

---

 

백준 1940번

https://www.acmicpc.net/problem/1940

1940번: 주몽

import sys
input=sys.stdin.readline
N=int(input())
M=int(input())
gabot=input().split()
answer=0
pointer1=0
pointer2=0

for i in range(N):
    pointer2=pointer1+1
    while(N>pointer2>pointer1):
        if int(gabot[pointer1])+int(gabot[pointer2])==M:
            answer+=1
        pointer2+=1
    pointer1+=1


print(answer)​

 

이 코드는 처음에 내가 짠 코드이다.

N<=2000일 때 N^2의 시간복잡도가 1초안에 풀리므로 N<=15000일때 N^2 알고리즘은 시간 초과가 날 수 밖에 없다.

따라서 다음의 코드로 고쳤다.

 

#입력 받기
import sys
input=sys.stdin.readline
N=int(input())
M=int(input())

#list에 int꼴로 저장하고 싶을 땐 이 코드가 가장 유용한 것 같다.
#cf) '1' 와 같은 문자형 숫자는 sort 시 아스키코드 크기 순으로 배열되므로
#0~9까지는 순서대로 배열되지만 10을 넘어가면 순서가 틀려진다!
gabot=list(map(int,input().split()))

answer=0
pointer1=0
pointer2=N-1

#리스트 sort해주기!
gabot.sort()

while(pointer2>pointer1):
    if gabot[pointer1]+gabot[pointer2]<M:
        pointer1+=1
    elif gabot[pointer1]+gabot[pointer2]>M:
        pointer2-=1
    else:
        answer+=1
        pointer1+=1
        pointer2-=1

print(answer)

바뀐 코드 중 가장 중요한 것은 sort를 했다는 점이다. 리스트 원소들의 합이 원하는 값인지 아닌지를 묻는 문제 이므로 각 원소들의 index는 바뀌어도 상관없다. 오름차순으로 정렬을 했기 때문에 포인터 두 개를 가지고 원하는 값을 찾아가게 된다.

---

백준 2018번

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

N=int(input())

count=1
start_index=1
end_index=1

#본인 수 미리 세두기
sum=1

while end_index!=N:
    if sum==N:
        count+=1
        end_index+=1
        sum+=end_index
    elif sum>N:
        sum-=start_index
        start_index+=1

    else:
        end_index+=1
        sum+=end_index

print(count)

 

위의 주몽 문제를 푼 방법가 거의 유사하게 풀면 쉽게 풀어낼 수 있다. 이때 문제 조건과 예시를 보면 N을 나타내는 방법에 N 본인도 포함되기 때문에 sum=1로 시작한다.

 

---

백준 1253번

https://www.acmicpc.net/problem/1253

1253번: 좋다

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

num.sort()
answer=0
for i in range(N):
    goodnum=num[i]
    start=0
    end=N-1

    while(start<end):
    	#음수까지 리스트에 포함되어 있어 sort후 goodnum의 한쪽 편만 순회하는 것이 의미 없다
        #따라서 end와 start는 goodnum을 넘어서도 리스트를 순회해야한다. 
        #end와 start가 goodnum을 가리키면 한칸 넘기고 다음 loop를 순회한다.
        if start==i:
            start+=1
            continue    
        elif end==i:
            end-=1
            continue

        if num[start] + num[end]==goodnum:
            answer+=1
            break
        elif num[start] + num[end]>goodnum:
            end-=1
        else:
            start+=1


print(answer)

이 문제는 goodnum을 넘어서 순회해야 하므로 continue를 쓴 부분이 중요하다.