이것이 코딩테스트다는 정말 도움이 되는 책이다. 하지만 난 이 책을 처음 볼 때 상당히 조급한 상태였고, 빨리 이론을 훑고나서 그래프, 구현 등 메이저한 실전 문제를 풀고 싶었다. 그래서 부록을 공부하지 않고 건너뛰는 무참한 실수를 벌이고 말았다.. 지금 다시 펼쳐보니 부록에 있는 건 이제 대부분 아는 내용이긴 하다. 그런데 생소한 게 하나 있었는데, 바로 투포인터에 대한 내용이다.
투 포인터
투 포인터란 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다. 예를 들어 1~10번 학생이 있을 때, "2번부터 7번까지 나와" 라고 하면 2번과 7번이라는 2개의 점을 이용해서 접근할 데이터의 범위를 표현한 것으로 볼 수 있다. 솔직히 이름 보면 이런 알고리즘이구나 정도는 예측 가능하다.
특정한 합을 가지는 연속 수열 찾기
그치만 투 포인터를 이용해 특정한 합을 가지는 연속 수열 찾기를 할 수 있는 건 꽤 신박하다.(양의 정수로 구성된 리스트 한정)
예를 들어 위와 같은 문제들을 말한다. 위 예제의 경우 답은 3이다.
어떻게 푸는가?
구체적인 알고리즘은 다음과 같다.
- 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다.
- 현재 부분합이 M과 같다면 카운트한다.
- 현재 부분합이 M보다 작으면 end를 1 증가시킨다.
- 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다.
- 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.
이 문제를 투 포인터 알고리즘으로 해결할 수 있는 이유는 기본적으로 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고, 끝점을 오른쪽으로 이동시키면 항상 합이 증가하기 때문이다. 그러므로 원소 내 음수 데이터가 포함되어 있는 경우 투 포인터 알고리즘으로 문제를 해결할 수 없다.
이런 건 한번 풀어봐야 각이 서는 법이다. 위 예제와 정확히 똑같은 문제가 있다. 백준 2003을 풀어보자.
n,m=list(map(int,input().split())) #데이터의 갯수, 부분합 M
data=list(map(int,input().split())) #전체 수열
count=0
interval_sum=0
end=0
#start를 차례대로 증가시키며 반복
#start 증가=interval_sum 감소
for start in range(n):
#해당 start를 고정시켜놓고, end를 가능한만큼 이동시키기
while interval_sum<m and end<n:
interval_sum+=data[end]
end+=1
#부분합이 m일때 카운트 증가
if interval_sum==m:
count+=1
#for문 돌면서 start를 1 증가시킬거니까 다음 반복문을 위해 마이너스
interval_sum-=data[start]
print(count)이후 응용문제인 백준 1806도 풀어보자.
#백준 1806
#합이 s 이상인 가장 짧은 수열의 길이 구하기!
n,s=list(map(int,input().split())) #데이터의 갯수, 부분합 M
data=list(map(int,input().split())) #수열 데이터
end=0
interval_sum=0
answer=n+1 #길이
for start in range(n):
while end<n and interval_sum<s:
interval_sum+=data[end]
end+=1
if interval_sum>=s:
answer=min(answer,end-start)
interval_sum-=data[start]
if answer==n+1:
print(0)
else:
print(answer)
참고: 이코테 472p
