기타 알고리즘: 투 포인터 알고리즘, 구간 합

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

 

투 포인터 알고리즘을 잘 활용할 수 있는 문제로는

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

 

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다.

2. 현재 부분 합이 M과 같다면, 카운트한다.

3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다.

4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다.

5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

 

n=5 #데이터의 개수 5개
m=5 #찾고자 하는 부분합 m=5

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
    
    if interval_sum==m:
        count+=1
    interval_sum-=data[start]

print(count)

---

구간 합 빠르게 계산하기

 

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

 

접두사 합을 활용한 알고리즘은 다음과 같다

 

N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장한다.

매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left-1]이다.

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])