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

(나동빈 님의 위 영상을 바탕으로 정리한 내용입니다.)

---

투 포인터 (Two pointers)

언제 쓰는가?

수열에서 특정한 합을 가지는 부분 연속 수열을 찾을 때

어떻게 구현하는가?

찾고자 하는 부분 연속 수열의 합을 M이라고 하자.

부분 연속 수열의 개수(count)를 가리키는 변수를 만든다.
시작점(start)과 끝점(end)를 가리키는 변수를 만든다.

• (현재 부분 합 == M) --> count += 1
• (현재 부분 합 <= M) --> end += 1
• (현재 부분 합 > M) --> start += 1

위 3줄을 모든 경우를 확인할 때까지 반복한다.

투 포인터 파이썬 코드

# n = 데이터의 개수, m = 구하고자 하는 부분 연속 수열의 합
n, m = 10, 6
data = [8, 4, 6, 2, 1, 10, 6, 2, 2, 4]

count = 0
partial_sum = 0
end = 0

for start in range(n):
    # end값을 가능한 만큼 증가시킨 다음
    while partial_sum < m and end < n:
        partial_sum += data[end]
        end += 1
    
    # 부분 합이 m이라면 카운트를 증가시킨다.
    if partial_sum == m:
        count += 1
    # start값을 1 증가시키기 전에 해당 수열의 값을 빼준다.
    partial_sum -= data[start]

print(count)

구간 합 (Prefix Sum)

언제 쓰는가?

수열에서 여러 개의 구간 합을 빠르게 계산할 때

어떻게 구현하는가?

구간 합 (Prefix Sum) : 해당 인덱스까지의 수열의 전체 합

예를 들어서 [10, 20, 30, 40, 50]이라는 수열이 있을 때,
이 수열의 구간 합은 [10, 30, 60, 100, 150]이다.

• 수열의 구간 합을 계산하여 배열 prefix_sum에 저장한다.

• 어떤 수열의 인덱스 l부터 인덱스 r까지의 합은
  prefix_sum[r] - prefix_sum[l - 1]으로 계산할 수 있다.

구간 합 파이썬 코드

# n = 데이터의 개수
n = 10
data = [8, 4, 6, 2, 1, 10, 6, 2, 2, 4]

sum = 0
prefix_sum = [0]

for i in data:
    sum += i
    prefix_sum.append(sum)

# 구간 합 계산 예시

left = 2
right = 7
print(prefix_sum[right] - prefix_sum[left - 1])