미리 더해두면 빨라진다냥! 누적합과 투 포인터
안녕, 나 코딩냥이다냥! 오늘은 이중 반복문이 시간 초과 날 때 꺼내는 무기 두 개를 배운다냥. 하나는 미리 더해두기(누적합), 하나는 두 손가락으로 훑기(투 포인터)라냥.
둘 다 O(n²) 를 O(n) 으로 줄여준다냥. 배열 문제의 절반은 이걸로 빨라진다냥.
오늘의 학습 목표
- 누적합으로 구간 합을
O(1)에 구한다. - 2차원 누적합으로 직사각형 합을 구한다.
- 투 포인터로 정렬된 배열을 한 번에 훑는다.
- 슬라이딩 윈도우로 조건을 만족하는 구간을 찾는다.
- 투 포인터가 안 되는 경우를 안다.
1단계 · 누적합이 뭐냥 (10분)
"3번째부터 7번째까지의 합"을 묻는 질문이 백만 번 들어온다냥. 매번 더하면 느리다냥. 그런데 미리 한 번 더해두면 질문마다 뺄셈 한 번이라냥.
비유로 이해하기 — 계단마다 적어둔 총거리
등산로 계단마다 "여기까지 몇 걸음" 이 적혀 있다냥. 그럼 3번 계단에서 7번 계단까지 몇 걸음인지 알려면? 7번의 숫자에서 2번의 숫자를 빼면 된다냥. 중간을 하나하나 안 세도 된다냥.
누적합이 정확히 이거라냥. pre[i] 에 처음부터 i번째까지의 합을
적어두는 거라냥.
pre = [0] * (n + 1)
for i in range(n):
pre[i + 1] = pre[i] + nums[i]그러면 l번째부터 r번째까지의 합은 뺄셈 하나로 나온다냥.
# l 번째부터 r 번째까지의 합 (1번부터 셀 때)
answer = pre[r] - pre[l - 1]pre[l - 1] 이지 pre[l] 이 아니라냥.
l번째 원소도 합에 포함해야 하기 때문이라냥. pre[l] 을 빼면 l번째를
실수로 빼버린다냥. 이 한 칸 차이가 가장 흔한 실수라냥.
오늘 1번 문제가 이걸 잡는다냥. pre 를 크기 n+1 로 잡고 pre[0] = 0
으로 두면 l = 1 일 때도 pre[0] 이 있어서 안전하다냥.
질의가 q개일 때, 매번 더하면 O(nq) 라냥. 누적합은 만드는 데 O(n),
질의마다 O(1) 이라 전체가 O(n + q) 라냥. n 과 q 가 크면 이 차이가
시간 초과와 통과를 가른다냥.
2단계 · 2차원으로 넓히기 (12분)
격자에서 직사각형 안의 합도 같은 방법으로 구한다냥. 다만 뺄 게 조금 많아진다냥.
pre[r][c] 에 (1,1) 부터 (r,c) 까지 직사각형의 합을 적어둔다냥.
pre = [[0] * (m + 1) for _ in range(n + 1)]
for r in range(1, n + 1):
for c in range(1, m + 1):
pre[r][c] = (grid[r-1][c-1] + pre[r-1][c]
+ pre[r][c-1] - pre[r-1][c-1])왜 - pre[r-1][c-1] 을 빼냥?
위쪽 직사각형 pre[r-1][c] 과 왼쪽 직사각형 pre[r][c-1] 을 더하면,
왼쪽 위 겹치는 부분이 두 번 더해진다냥. 그래서 한 번 빼주는 거라냥.
이걸 포함-배제라고 한다냥. 더한 걸 다시 빼서 겹침을 정리하는 거라냥.
직사각형 (r1,c1)~(r2,c2) 의 합도 같은 원리라냥.
answer = (pre[r2][c2] - pre[r1-1][c2]
- pre[r2][c1-1] + pre[r1-1][c1-1])부호가 헷갈리면 그림을 그려보자냥. 큰 사각형에서 위 띠와 왼쪽 띠를 빼면 왼쪽 위 모서리가 두 번 빠진다냥. 그래서 마지막에 한 번 더해준다냥.
오늘 2번 문제가 이 부호를 정확히 잡는다냥.
3단계 · 투 포인터 (12분)
이제 다른 무기라냥. 두 개의 손가락으로 배열을 훑는 거라냥. 정렬된 배열에서 특히 강하다냥.
"두 수를 골라 합이 정확히 k 인 쌍"을 찾는다냥. 이중 반복문은 O(n²)
이라냥. 그런데 정렬해두면 양쪽 끝에서 손가락 두 개로 한 번에 훑을 수 있다냥.
a.sort()
lo, hi = 0, n - 1
while lo < hi:
s = a[lo] + a[hi]
if s == k:
# 찾았다냥
lo += 1
hi -= 1
elif s < k:
lo += 1 # 합이 작으니 왼쪽을 키운다냥
else:
hi -= 1 # 합이 크니 오른쪽을 줄인다냥합이 목표보다 작으면 더 큰 수가 필요하니 lo 를 오른쪽으로 (큰 쪽으로)
옮긴다냥. 크면 hi 를 왼쪽으로 (작은 쪽으로) 옮긴다냥.
두 손가락이 한 방향으로만 움직이니 전체가 O(n) 이라냥. 정렬
O(n log n) 을 더해도 이중 반복문보다 훨씬 빠르다냥.
투 포인터가 성립하려면 정렬이 필요하다냥.
"합이 작으면 왼쪽을 키운다"는 판단은 배열이 정렬돼 있어야 옳다냥. 정렬 안 된 배열에서 이러면 엉뚱한 걸 건너뛴다냥.
오늘 3번 문제의 큰 입력은 이중 반복문으로는 시간 초과라냥. 투 포인터로만 통과한다냥.
4단계 · 슬라이딩 윈도우 (12분)
투 포인터의 사촌이라냥. 두 손가락이 같은 방향으로 가면서, 그 사이를 창문처럼 넓혔다 줄였다 하는 거라냥.
"합이 S 이상인 가장 짧은 연속 구간"을 찾는다냥.
lo = 0
cur = 0
best = n + 1
for hi in range(n):
cur += a[hi] # 오른쪽으로 넓힌다냥
while cur >= S:
best = min(best, hi - lo + 1)
cur -= a[lo] # 되는 동안 왼쪽을 줄인다냥
lo += 1오른쪽 hi 를 한 칸씩 넓히며 합을 더한다냥. 합이 S 이상이 되면, 그때부터
왼쪽 lo 를 줄이며 더 짧게 만들 수 있는지 본다냥.
두 손가락 다 오른쪽으로만 가니 전체가 O(n) 이라냥.
이게 되는 건 값이 전부 양수라서라냥.
양수면 창을 넓히면 합이 반드시 커지고, 줄이면 반드시 작아진다냥. 이 단조로움 덕에 왼쪽을 한 방향으로만 밀어도 된다냥.
오늘 4번 문제가 "양수"를 못 박아둔 이유가 이거라냥. 음수가 섞이면 이 방법이 깨진다냥 — 그게 5단계라냥.
5단계 · 투 포인터가 안 될 때 (12분)
오늘의 마지막이자 제일 중요한 이야기라냥. 투 포인터와 슬라이딩 윈도우는 만능이 아니라냥. 언제 안 되는지 알아야 한다냥.
"합이 정확히 K 인 연속 구간의 개수"를 세는데, 이번엔 음수가 섞여 있다냥.
음수가 있으면 슬라이딩 윈도우가 깨진다냥.
창을 넓혔는데 음수를 만나면 합이 오히려 줄어든다냥. "합이 크면 왼쪽을 줄인다"는 판단이 더 이상 맞지 않는다냥. 줄였다가 다시 늘려야 할 수도 있는데, 한 방향으로만 가는 투 포인터는 그걸 못 한다냥.
그럼 어떻게 하냥? 누적합으로 돌아간다냥. 구간 (i, j] 의 합은
pre[j] - pre[i] 라냥. 이게 K 가 되는 (i, j) 쌍을 세면 된다냥.
from collections import defaultdict
seen = defaultdict(int)
seen[0] = 1 # 빈 접두사 (아무것도 안 더한 상태) 하나
pre = 0
cnt = 0
for v in a:
pre += v
cnt += seen[pre - K] # pre - K 가 나온 횟수만큼 구간이 있다냥
seen[pre] += 1지금까지의 누적합 pre 를 딕셔너리에 세어둔다냥. 새 위치에서 pre - K
라는 누적합이 몇 번 나왔는지 세면, 그게 곧 여기서 끝나는 합 K 짜리
구간의 개수라냥.
5장의 딕셔너리가 여기서 다시 쓰인다냥. 전체가 O(n) 이라냥.
정리하면 이렇게 고르자냥.
- 값이 전부 양수고 "조건을 만족하는 구간" → 슬라이딩 윈도우
- 정렬된 배열에서 "두 수의 합" → 투 포인터
- 음수가 섞이거나 "정확히 K인 구간의 개수" → 누적합 + 딕셔너리
오늘 4번(양수, 윈도우)과 5번(음수, 누적합)이 거의 같은 질문인데 방법이 갈리는 이유가 이거라냥.
오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개라냥. 1번은 누적합, 2번은 2차원 누적합, 3번은 투 포인터, 4번은 슬라이딩 윈도우, 5번은 음수 때문에 투 포인터가 안 되는 경우라냥.
4번과 5번을 나란히 풀어보면 "언제 윈도우가 되고 언제 안 되는지"가 손에 잡힌다냥. 가보자냥~