투 포인터에 대해 (백준 2003,1806)

이것이 코딩테스트다는 정말 도움이 되는 책이다. 하지만 난 이 책을 처음 볼 때 상당히 조급한 상태였고, 빨리 이론을 훑고나서 그래프, 구현 등 메이저한 실전 문제를 풀고 싶었다. 그래서 부록을 공부하지 않고 건너뛰어 버렸다.. 지금 다시 펼쳐보니 부록에 있는 건 이제 대부분 아는 내용이긴 하다. 그런데 생소한 게 하나 있었는데, 바로 투포인터에 대한 내용이다.

투 포인터

투 포인터란 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다. 예를 들어 1~10번 학생이 있을 때, "2번부터 7번까지 나와" 라고 하면 2번과 7번이라는 2개의 점을 이용해서 접근할 데이터의 범위를 표현한 것으로 볼 수 있다. 솔직히 이름 보면 이런 알고리즘이구나 정도는 예측 가능하다.

특정한 합을 가지는 연속 수열 찾기

그치만 투 포인터를 이용해 특정한 합을 가지는 연속 수열 찾기를 할 수 있는 건 꽤 신박하다.(양의 정수로 구성된 리스트 한정)

예를 들어 위와 같은 문제들을 말한다. 위 예제의 경우 답은 3이다.

어떻게 푸는가?

구체적인 알고리즘은 다음과 같다.

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다.
2. 현재 부분합이 M과 같다면 카운트한다.
3. 현재 부분합이 M보다 작으면 end를 1 증가시킨다.
4. 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 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

이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다.