목차
1. 투 포인터
2. 그림으로 이해
3. 코드
4. 느낀점
투 포인터
투 포인터는 간단한 알고리즘 기법 중 하나이다.
투 포인터는 두개의 포인트 지점을 지정한 후 조건에 맞게 유동적으로 움직일 수 있다는 특징이 있다.
말로 설명하기 보다 그림으로 바로 이해해도 무관하기 때문에 바로 그림과 예시 문제로 이해해 보자.
그림으로 이해
문제를 가정하고 그 문제를 해결하면서 투 포인터를 이해해보자.
문제
n과 m이 주어진다.
이때 1부터 n까지 공차가 1인 등차수열이 차례대로 리스트에 저장된다.
이 리스트에서 부분합이 m이 되는 경우의 수를 출력하시오.
(단, m <= n)
풀이
우리는 투 포인터 기법을 이용하여 풀 것이다.
아래 그림은 n = m = 4인 상황을 나타낸 것이다.
부분 합을 저장할 S 변수는 3부터 시작해야 한다.
start = 1, end = 2로 시작을 한다.
투 포인터 작동 원리는 다음과 같다.
- S > m : S -= start, start += 1
- S < m : end += 1, S += end
- S = m : count += 1, end += 1, S += end
- 종료 조건 : start >= end or end == n
아래 그림과 같이 start와 end를 각각 1,2로 초기화 한 후 시작한다.
처음 S = 3으로 초기화한다.
이 때 S < m 이므로 앞선 작동 방식을 적용하면
end += 1을 한 후 S += end가 된다. 이 때 S값은 3으로 아직 S < m임을 알 수 있고 다시 작동 방식을 따라가면 된다.
이번엔 S > m이니 S -= start를 한 후 start += 1을 한다.
이 방식을 계속 반복하다 보면 최종적으로 end = 4에 있으면 종료하게 된다.
코드
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
start = 1
end = 2
S = 3
count = 1
while start < end and end != n:
if S > m:
S-= start
start += 1
elif S < m:
end += 1
S += end
else:
count += 1
end += 1
S += end
print(count)count가 1로 시작되는 이유는 while문을 돌면서 길이가 1인 부분합을 구할 수는 없기 때문이다.
start = end = S = 1로 잡고 푸는 방식도 있다.(사실 이게 더 많이 쓰인다)
다만 이때에는 while문의 조건이 수정되어야 한다.
느낀점
설명하면서 꼬인 느낌이 난다.
원래는 더 간단하고 이해하기 쉽도록 설명해보고 싶었는데 잘 되지 않았다. 내가 아는 것과 누군가를 가르치는 것은 다른 문제라는 것을 알게되었다.
글을 쓰면서 투 포인터에 대해 더 이해할 수 있었다.
