코딩 테스트 입문 ⑭ 누적 합, 투 포인터, 슬라이딩 윈도우

1. 누적 합

11659

2435

import sys import collections sys.setrecursionlimit(1000) input = sys.stdin.readline n, m = map(int, input().split()) a = list(map(int, input().split())) for i in range(m) :     x, y = map(int, input().split())     s = 0     for i in range(x-1,y) :         s += a[i]     print(s) --------------- 속도 개선 : 누적합으로 저장 ---------------- import sys input = sys.stdin.readline n, m = map(int, input().split()) a = list(map(int, input().split())) b = [0]  nex = 0 for x in a :     b.append(b[-1]+x) for i in range(m) :     x, y = map(int, input().split())     print(b[y]-b[x-1])

import sys import collections sys.setrecursionlimit(1000) input = sys.stdin.readline n, m = map(int, input().split()) a = list(map(int, input().split())) b = [] for i in range(1, n) :     c = a[i-1]+a[i]     b.append(c) print(max(b)) ----------------------------- 누적합으로 저장 ----------------------------- import sys input = sys.stdin.readline n, m = map(int, input().split()) a = list(map(int, input().split())) b = [0] r = [] for x in a :     c = b[-1]+x     b.append(c)      for i in range(m, n+1) :     e = b[i]-b[i-m]     r.append(e) print(max(r))

2. 투 포인터

11728

2003

import sys input = sys.stdin.readline n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) res = [] i, j = 0, 0 while i < n and j < m :     if a[i] < b[j] :         res.append(a[i])         i += 1     else :         res.append(b[j])         j += 1 if i == n :     while j <m :         res.append(b[j])         j+=1 else :     while i <n :         res.append(a[i])         i+=1 print(*res)

import sys input = sys.stdin.readline n, m = map(int, input().split()) a = list(map(int, input().split())) + [300000001] i, j = 0, 0 now = a[0] res = 0 while j < n :     if now == m :         res += 1         now -= a[i]         i += 1         j += 1         now += a[j]     elif now < m :         j += 1         now += a[j]     else :         now -= a[i]         i += 1 print(res)

3. 슬라이딩 윈도우

12847	2559
import sys input = sys.stdin.readline n, m = map(int, input().split()) a = list(map(int, input().split())) now = sum(a[:m]) res = now for i in range(m, n) :     now += a[i]     now -= a[i-m]     res = max(now, res) print(res)	import sys input = sys.stdin.readline n, m = map(int, input().split()) a = list(map(int, input().split())) now = sum(a[:m]) res = now for i in range(m, n) :     now += a[i]     now -= a[i-m]     res = max(now, res) print(res)