투 포인터(Two Point)

 

출처 : https://www.youtube.com/watch?v=ttLRltNDiCo&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=40 

 

 

• 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.
• 흔히 2, 3, 4, 5, 6, 7번 학생을 지목해야 할 때 간단히 "2번부터 7번까지의 학생"이라고 부르곤 한다.
• 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

 

투 포인터 문제를 활용해서 해결할 수 있는 가장 대표적인 문제는 특정한 합을 가지는 부분 연속 수열 찾기 문제이다.

(부분 연속 수열이란, 하나의 수열이 있을 때 그 수열에서 연속된 일부분의 데이터만을 가지는 수열을 의미한다.)

 

N개의 자연수로 구성된 수열이 있을 때, 합이 M인 부분 연속 수열의 개수를 구하는 문제를 살펴보자. 수행 시간 제한은 O(N)이다.

 

완전 탐색 알고리즘을 사용하면 O(N^2)의 시간이 걸리게 된다. 선형 시간에 동작하는 알고리즘으로 만들기 위해서 투 포인터를 활용한다.

 

투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있다.

1. 시작점(Start)와 끝점(End)이 첫 번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면, 카운트를 1 증가시키고 Start를 1 증가시킨다.
3. 현재 부분 합이 M보다 작다면, End를 1 증가시킨다.
4. 현재 부분 합이 M보다 크다면, Start를 1 증가 시킨다.
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

 

• [초기 단계] 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.
  • 현재의 부분합이 1로 목표인 5보다 작으므로 카운트를 증가시키지 않는다.

 

• [Step 1] 이전 단계에서의 부분합이 1로 목표인 5보다 작았기 때문에 End를 오른쪽으로 1 증가시킨다.
  • 현재의 부분합이 1+2 = 3으로 5보다 작으므로 카운트를 증가시키지 않는다.

 

• [Step 2] 이전 단계에서의 부분합이 3이었기 때문에 End를 오른쪽으로 1 증가시킨다.
  • 현재의 부분합은 6으로 5보다 크기 때문에 카운트를 증가시키지 않는다.

 

• [Step 3] 이전 단계에서의 부분합이 6으로 목표값인 5보다 컸기 때문에 Start를 1 증가시킨다.
  • 현재의 부분합이 5이므로 카운트를 1 증가시킨다.

 

 

• [Step 4] 이전 단계에서의 부분합이 5였기 때문에 Start를 1 증가시킨다.
  • 현재의 부분합은 3으로 5보다 작기 때문에 카운트를 증가시키지 않는다.

 

• [Step 5] 이전 단계에서의 부분합이 3으로 5보다 작았기 때문에 End를 1 증가시킨다.
  • 현재의 부분합이 5이므로 카운트를 1 증가시킨다.

 

• [Step 6] 이전 단계에서의 부분합이 5였기 때문에 Start를 1 증가시킨다.
  • 현재의 부분합이 2로 5보다 작으므로 카운트를 증가시키지 않는다.

 

• [Step 7] 이전 단계에서의 부분합이 2였기 때문에 End를 1 증가시킨다.
  • 현재의 부분합이 7로 5보다 크므로 카운트를 증가시키지 않는다.

 

• [Step 8] 이전 단계에서의 부분합이 7였기 때문에 Start를 1 증가시킨다.
  • 현재의 부분합이 5이므로 카운트를 1 증가시킨다.

 

특정한 값을 가지는 부분 연속 수열 찾기 파이썬 코드

n = int(input())
m = int(input())
array = list(map(int, input().split()))

count = 0
summ = 0
e = 0

for start in range(n):
    # 현재 부분수열의 합이 m보다 작고 End가 n보다 작으면
    while summ < m and e < n:
        # 현재 부분수열의 e번째 인덱스 값을 더하고 End를 1증가시킨다.
        summ += array[e]
        e += 1
    if summ == m:
        count += 1
    # 현재 부분수열의 합이 m보다 크거나 같으면 start는 1증가하고 기존의 start번째 인덱스 값을 뺀다.
    summ -= array[start]

print(count)