[Algorithm] day7. Prefix Sum, Two Pointer

Prefix Sum

배열의 누적 합을 저장해 놓음으로써, 구간 합을 O(1)에 구하는 테크닉이다.

구간 [1,i]의 원소의 합을 p[i]로 정의하면, 구간 [j,i]의 합은 p[i] - p[j-1]이다.

• 전처리 : O(N)
• 구간 합 : O(1)

temp = 0
for i in nList:
    temp += i
    prefix_sum.append(temp)
# 예시의 경우, 최종 prefix_sum은 [0, 5, 9, 12, 14, 15] 이다.

for _ in range(m):
    i, j = map(int, input().split())
    print(prefix_sum[j] - prefix_sum[i-1])

예를 들어, (x1, y1)부터 (x2, y2)의 원소를 모두 합친 값은
pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1]

arr = []
for i in range(n):
    a = list(map(int, input().split()))
    arr.append(a)

dp = [[0]*(n+1) for i in range(n+1)] #2차원 배열 선언

# N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다.
for i in range(1, n+1):
     for j in range(1, n+1):
           dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i-1][j-1]

# M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어진다.
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1])

배열의 값이 변하지 않는다면, 누적 합을 이용하고
배열의 값이 변한다면, Segment Tree를 배워야 한다.

Two Pointer

배열 내에서 원소를 가리키는 2개의 포인터를 조작하면서 문제를 해결하는 테크닉이다.
자료가 1차원으로 주어진 문제에서 생각해볼 수 있다.

예를 들어, N개의 수로 된 수열 A[1], A[2], .. , A[N]이 있고 이 수열의 A[i] ~ A[j]까지의 합이 M이 되는 경우의 수를 찾는 경우를 살펴보자.

투포인터로 접근 시, a[i]는 자연수이므로 l번째 수부터 r번째 수까지의 합이 M보다 크면, i번째 수부터 r번째 수까지의 합은 무조건 M보다 크다. (i < l)
따라서, 합이 M보다 큰 [l,r] 구간을 찾았다면, [i,r] 구간은 볼 필요가 없다. 시간복잡도는 O(2n) = O(n) 이다.

for start in range(len(data)):
    while interval_sum < answerSum and end < len(data):
        interval_sum += data[end]
        end += 1
    if interval_sum == answerSum:
        count += 1
    interval_sum -= data[start]