[알고리즘] 투포인터, 슬라이딩 윈도우, 누적합, 구간합

투포인터

• 배열에서 이중 for문으로 O(N^2) 시간복잡도를 가진 탐색을 하는 문제에서 포인터 2개를 사용해 O(N)으로 해결하는 알고리즘

 

슬라이딩 윈도우(Sliding Window)

• 투 포인터와 비슷하지만, 고정 사이즈의 윈도우를 이동시키는 알고리즘
• 정렬된 배열이 아니여도 사용 가능

 

구간합(prefix sum)

• 수열에서 특정 구간의 합
• i ~ j 번째 인덱스 값들의 값

 

부분합(partial sum)

• 0 ~ n 번째 인덱스 값들의 합

---

 

누적합(prefix)

• 수열의 특정 구간의 값을 구하는 요청이 여러개인 경우 시간 복잡도를 O(N^2)에서 O(N)으로 줄이기 위해 사용된다.

 

누적합의 성질

• 1차원 배열 공간 복잡도는 O(n), 2차원의 공간 복잡도 O(n^2)
• 계산은 O(1) 시간 복잡도
• 합을 구하는 도중에 배열의 값이 변경되면 세그먼트 트리 사용

sumArr[0] = arr[0]
sumArr[i] = sumArr[i-1] + arr[i]
sumArr[n] = arr[0] + arr[1] + ... + arr[n-1] + arr[n]
sumArr[j]-sumArr[i] = arr[i] + arr[i+1] + ... + arr[j-1] + arr[j]

 

누적합 문제 예시 - 1차원 배열

• index 3~5의 값
  • arr[3] + arr[4] + arr[5] = 6 + 10 + 3 = 19
  • sumArr[5] - sumArr[2] = 31 - 12 = 19 

index	0	1	2	3	4	5
배열 arr	3	5	4	6	10	3
누적합 sumArr	3	8	12	18	28	31

 

누적합 문제 예시 - 2차원 배열

• 2차원 배열

index	0	1	2	3	4
0	3	5	4	3	4
1	5	7	10	5	7
2	3	3	6	6	8
3	6	6	8	9	4
4	5	2	7	3	5

• 첫 번째로 행끼리 누적합을 구해준다.

index	0	1	2	3	4
0	3	8	12	15	19
1	5	12	22	27	34
2	3	6	12	18	26
3	6	12	20	29	33
4	5	7	14	17	22

• 두 번째로 열끼리 누적합을 구해준다.

index	0	1	2	3	4
0	3	8	12	15	19
1	8	20	34	42	53
2	11	26	46	60	79
3	17	38	66	89	112
4	22	45	80	106	134

 

• (3,3)에서 (4,4) 노란색 부분의 합을 구하려고 할 때
• sumArr[x2][y2] - sumArr[x2][y-1] - sumArr[x1][y2] + sumArr[x1-1][y1-1]
• sumArr[4][4](전체) - sumArr[4][2](초록색) - sumArr[2][4](파란색) + sumArr[2][2] = 노란색 구역의 합
• 빨간색 영역은 초록색과 파란색 영역의 누적합을 뺄 때 제거된다. 
• 두 영역에서 빨간색 영역을 두 번 빼줬기 때문에 한 번 더해준다.

---

투포인터 문제 - 2230번 수 고르기

https://www.acmicpc.net/problem/2230

2230번: 수 고르기

 

n, m = 5, 3  # 정수 개수, 두 개의 정수 차이 최소 기준
arr = [1, 2, 3, 4, 5]
#n, m = map(int, input().split())
#arr = [int(input()) for _ in range(n)]
arr.sort()
lt = 0
rt = 0
minValue = float('inf')
# print(arr)
while rt != n and lt <= rt:
    value = arr[rt] - arr[lt]
    if value >= m:  # m 이상일 때
        minValue = min(minValue, value)
        lt += 1
    else:  # m 이상이 아닐 때
        rt += 1
print(minValue)

 

투포인터 문제 - 1806번 부분합

https://www.acmicpc.net/problem/1806

1806번: 부분합

 

#n, s = 10, 15
#arr = [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]
n, s = map(int,input().split())
arr = list(map(int,input().split()))

lt = 0
rt = 0
minLen = float('inf')
value = 0

while True:
    # 수들의 합이 s를 넘으면 최소값을 계산
    # 안넘으면 rt 값 증가
    if value >= s:
        minLen = min(minLen, (rt - lt))
        value -= arr[lt]
        lt += 1
    elif rt == n:
        break
    else: # value < s:
        value += arr[rt]
        rt += 1

if minLen == float('inf'):
    minLen = 0

print(minLen)

 

누적합 문제 - 11660번 구간 합 구하기 5

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

import sys
# n, m = 4, 3 # 표의 크기, 연산 횟수
n, m = map(int, input().split())
arr = [[0]*(n+1)] + list([0]+list(map(int, input().split())) for _ in range(n))
sumArr = [[0]*(n+1) for _ in range(n+1)]

# 누적합 배열 만들기
for i in range(1, n+1):
    for j in range(1, n+1):
        sumArr[i][j] = sumArr[i-1][j] + sumArr[i][j-1] - sumArr[i-1][j-1] + arr[i][j]

# 계산 하기 - (x1, y1) 부터 (x2, y2) 합 구하기
# 전체 - 영역1 - 영역2 + (영역1과 영역2에서 두번 빼줬기 때문에 더해줘야 하는 영역)
for _ in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    res = sumArr[x2][y2] - sumArr[x1-1][y2] - sumArr[x2][y1-1] + sumArr[x1-1][y1-1]
    print(res)