투포인터 알고리즘 & 부분합 알고리즘

1. 투포인터 알고리즘

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

 

start와 end 포인터를 움직여가며 빨간 네모 안의 합을 찾아가는 알고리즘

*빨간네모의 합은 코드의 summary 

#데이터의 개수 n, 부분 연속 수열의 합 m
n, m=5,5
data=[1,2,3,2,5]
 
result=0
summary=0
end=0
 
for start in range(n):
    while summary<m and end<n:
        summary+=data[end]
        end+=1
    if summary==m:
        result+=1
    summary-=data[start]
 
print(result)

 

2. 부분합 알고리즘

R까지의 누적합 - (L-1)까지의 누적합을 빼주면

빨간색 박스 안의 누적합이 나온다

 

#데이터 개수 n n=5 data=[10, 20, 30, 40, 50]   summary=0 prefix_sum=[0] for i in data:     summary+=i     prefix_sum.append(summary)   #구간합 계산 left=3 right=4 print(prefix_sum[right]-prefix_sum[left-1])

cs

print 하면 70이 나온다

 

 

출처 : youtu.be/rI8NRQsAS_s