투 포인터 유형 문제

😎 투 포인터

투 포인터 알고리즘이란, 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.

흔히 2,3,4,5,6,7번 학생을 지목해야 할 때 간단히 2번부터 7번까지의 학생이라고 부르곤 한다.

리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

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

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

😓 데이터의 개수만큼 원소를 확인하며 선형적으로 동작하는 알고리즘은 완탐으로는 N^2이다.
이럴 때 투 포인터 알고리즘을 사용해서 풀면 돼

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

투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있다.
1. 시작점(start)과 끝점(end)이 첫번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면 카운트
3. 현재 부분 합이 M보다 작다면, end + 1
4. 현재 부분 합이 M보다 크거나 같다면, start + 1
5. 모든 경우를 확인할 때까지 2~4 과정 반복

• 2,3,4번 과정을 반복하면 이 문제의 최적의 해를 구할 수 있다.

😁 여기서 현재 부분 합이 M보다 작으면, end를 증가시키는데 --> 끝점을 증가시키는 건 현재 부분 합이 증가하는 것을 의미하고, start를 증가시키는 건 현재 부분합을 감소시키는 것을 의미한다.

그렇기 때문에 매번 현재의 부분합과 M의 값을 비교해서 그 시작점과 끝점의 위치를 바꾸는 방법을 이용해서 최적의 해를 구할 수 있다.

예제 문제 - 특정한 합을 가지는 부분 연속 수열 찾기

• 투 포인터 알고리즘의 대표적인 문제
  😊 어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제.

😁 투 포인터 알고리즘 소스코드

# sys.stdin = open("input.text", "rt")
n = 5 # 데이터의 개수 N
m = 5 # 찾고자하는 부분합 M
 
count = 0
interval_sum = 0
end = 0
 
# start를 차례대로 증가시키며 반복
for start in range(n):
    # end만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start] # 같은 경우는 큰 경우든 빼주고 다음으로 넘어가야해
 
print(count)

• 내가 풀어본 코드

N, M = map(int, input().split())
data = list(map(int, input().split()))

cnt = 0
s = 0
e = 1
res = data[0]  #시작 값

while True:
    if res < M:
        if e < N:  #이 경우에만 더해줘야지
            res += data[e]
            e += 1
        else:  #end 부분이 N이 된 경우
            break
    elif res == M:
        cnt += 1
        res -= data[s]
        s += 1
    else:
        res -= data[s]
        s += 1

print(cnt)

나한테 맞는 코드를 택하자.