[알고리즘] 투 포인터 알고리즘, 구간 합 계산

자료 출처: https://youtu.be/cswJ1h-How0

1. 투 포인터 알고리즘 예시 문제: 특정한 합을 가지는 부분 연속 수열 찾기

• start, end가 0번째 인덱스를 가리키도록 함 (start <= end)
• 현재 부분 합이 M과 같다면 카운트해줌
• 현재 부분 합이 M보다 작다면 end += 1
• 현재 부분 합이 M보다 크다면 start += 1
• 모든 경우를 확인할 때까지 2~4번 과정을 반복한다.

n = 5
m = 5
data = [1, 2, 3, 2, 5]

count = 0
interval_sum = 0
end = 0

# 모든 원소 각각을 iteration마다 시작 인덱스로 하나씩 고정해놓고
for start in range(n): 

    # end를 가능한 만큼 이동시키기
    # 이때 interval_sum이 m보다 커져서 while문을 벗어나게 되는 경우에는?
    # start는 for문 안에서 고정에 end += 1을 계속 해봤자 interval_sum은 계속 커질 것이기 때문에 더 볼 필요 없음
    # (data의 모든 원소가 양수라는 전제)
    while end < n and interval_sum < m:
        interval_sum += data[end]
        end += 1
    
    if interval_sum == m:
        count += 1
        
    # 이제 while문을 빠져나오고 for문은 다음 iteration으로 가야 하기 때문에 그 전에 처리할 것을 처리해줌
    # 즉 기존의 start 인덱스의 원소를 interval_sum에서 빼준 후 start 인덱스를 다음 인덱스로 넘긴다.
    interval_sum -= data[start]
    
print(count)

2. 구간 합

연속적으로 나열된 n개의 수중 특정 구간의 모든 수를 합한 값을 계산

• n개의 정수로 구성된 수열
• m개의 쿼리 정보: 각 쿼리는 left, right로 구성되며, 각 쿼리에 대하여 [left, right] 구간에 포함된 데이터들의 합을 출력
• 수행 시간 제한: O(n + m)
• 접두사 합(Prefix Sum): 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해놓은 것
  • n개의 수의 위치 각각에 대하여 접두사 합을 계산하여 별도의 배열 P에 저장
  • 매 m개의 쿼리 정보를 확인할 때 구간 합은 P[right] - P[left - 1]

n = 5
data = [10, 20, 30, 40, 50]

sum_value = 0
prefix_sum = [0] # 인덱스 0부터 시작(data의 인덱스보다 앞에 하나 더 있다고 생각하기)

for i in data:
    sum_value += i
    prefix_sum.append(sum_value)
    
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])