[코테] 투포인터 알고리즘

투포인터 알고리즘

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

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

• N개의 자연수로 구성된 수열이 있습니다.
• 합이 M인 부분 연속 수열의 개수를 구해보세요
• 수행 시간 제한은 O(N) 입니다.
  - 부분 연속 수열이란 수열에서 연속된 일부분의 데이터만 갖는 수열입니다.
  

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

구현 코드)

# -*- coding: utf-8 -*-
n = 5 # 데이터 개수
m = 5 # 찾고자 하는 부분합 M
data = [1,2,3,2,5]

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)

구간 합 빠르게 계산하기

아이디어 )
접두사 합 (Prefix Sum) : 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것

• 접두사 합을 이용한 알고리즘
  - N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장합니다
  • 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left-1] 입니다.
    

구현 코드)

# -*- coding: utf-8 -*-
# 데이터 개수 N과 데이터 입력
n = 5
data = [10,20,30,40,50]

# 접두사 합 배열 계산
sum_value = 0 
prefix_sum = [0]
for i in data :
    sum_value += i
    prefix_sum.append(sum_value)

# 구간 합 계산
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left-1])

참고 : https://www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9