[알고리즘 마스터] 10. 투 포인터

안녕하세요. 개발감자 박그냥입니다!🥔

오늘은 알고리즘 중 투 포인터에 대해 정리해보도록 하겠습니다.

이 포스팅은 책 <Do it! 코딩테스트>를 참고하여 제작되었습니다.

 

1. 투 포인터

2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다고 합니다. 굉장히 간단한 알고리즘입니다.

백준의 문제 중 투 포인터를 활용하는 문제를 풀며 이해해보도록 할까요?

1-1. 투 포인터 백준 문제 

2018번 연속된 자연수의 합 구하기

 

인증

1-2. 문제 풀이

투 포인터라는 것은 말 그대로 포인터(가르키는 것)이 2개라는 의미입니다. 위의 문제에서 투 포인터를 각각 자연수의 합의 가장 작은 숫자와 가장 큰 숫자를 가르키는 것으로 활용합니다. 두 개의 포인터를 이용해서 내가 원하는 값이 나왔는지 계속 확인하고, 내가 원하는 값이면 가지수에 +1을 해주며 가장 마지막 포인터를 더해주고, 숫자의 합도 더해줍니다.

합이 내가 원하는 값보다 크면 현재의 start_index가 가르키는 숫자를 빼주고 start_index의 값을 +1 해줍니다.

이외의 경우에는 가장 마지막 포인터를 더해주고, 숫자의 합도 더해줍니다.

 

이 과정을 계속하다보면, end_index가 n인 경우에 이 반복문은 멈추게 되고, 그 때의 가지수를 출력하게 됩니다.

더 정확한 풀이는 책을 참고하시면 좋겠습니다. 여기서 중요한 점은 투 포인터의 활용입니다.

처음과 끝을 가르키는 포인트를 투포인터의 개념을 통해 구현한 것입니다.

 

아래는 제가 책을 참고하여 푼 파이썬 코드입니다. 공부하시는 분들께 도움이 되었으면 좋겠습니다.

import sys

input = sys.stdin.readline
N = int(input())
start_index = 1
end_index = 1

count = 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)

그럼 더 유익한 포스팅으로 돌아올게요. 개발감자였습니다!