직접 풀어보자! 누적합과 투 포인터 5문제

안녕, 나 코딩냥이다냥! 오늘 문제는 이중 반복문으로 짜면 시간 초과가 나도록 크게 잡아뒀다냥. 그러니 배운 무기를 꼭 써야 한다냥.

풀기 전에 정하자냥 — 누적합이냥, 투 포인터냥, 슬라이딩 윈도우냥?

어떤 무기를 고를지

"구간의 합을 여러 번 묻는다" → 누적합
"정렬된 배열에서 두 수" → 투 포인터
"양수 배열에서 조건을 만족하는 구간" → 슬라이딩 윈도우
"음수가 섞였다" → 누적합 + 딕셔너리

미션 1구간 합 구하기15분

질의마다 l번째부터 r번째까지의 합을 구한다냥.

뼈대한 번 더해두고, 질의마다 뺄셈 하나라냥

pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] + nums[i]

# 질의 (l, r) 마다
print(pre[r] - pre[l - 1])

질의가 많으니 매번 더하면 시간 초과라냥. 누적합은 질의마다 뺄셈 하나라냥.

pre[l - 1] 이라냥. pre[l] 이 아니라냥.

l번째 원소를 포함해야 하니 그 앞까지의 누적합을 빼야 한다냥. 한 칸 어긋나면 모든 질의가 틀린다냥. 공개된 예시 1 3 → 6 으로 바로 확인하자냥.

입력이 크니 input() 을 반복 호출하면 느리다냥. 파이썬이면 sys.stdin 으로 한 번에 읽자냥.

import sys
data = sys.stdin.buffer.read().split()

미션 22차원 구간 합20분

질의마다 직사각형 안의 수의 합을 구한다냥.

문제 풀러 가기

뼈대누적합 격자를 만든다냥

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][c] 는 (1,1) 부터 (r,c) 까지의 합이라냥.

직사각형 합의 부호를 조심하자냥.

ans = (pre[r2][c2] - pre[r1-1][c2]
       - pre[r2][c1-1] + pre[r1-1][c1-1])

위 띠와 왼쪽 띠를 빼면 왼쪽 위 모서리가 두 번 빠진다냥. 그래서 마지막에 한 번 더해준다냥. 부호를 틀리면 공개된 첫 예시부터 틀린다냥.

미션 3두 수의 합20분

합이 정확히 k 가 되는 쌍의 개수를 센다냥.

문제 풀러 가기

뼈대정렬하고 양쪽 끝에서 좁혀온다냥

a.sort()
lo, hi, cnt = 0, n - 1, 0
while lo < hi:
    s = a[lo] + a[hi]
    if s == k:
        cnt += 1
        lo += 1
        hi -= 1
    elif s < k:
        lo += 1
    else:
        hi -= 1

합이 작으면 왼쪽을 키우고, 크면 오른쪽을 줄인다냥. 값이 서로 달라서 중복 세기 걱정이 없다냥.

이중 반복문으로 짜면 시간 초과라냥.

n 이 만 개라 O(n²) 는 1억 번이라냥. 정렬 후 투 포인터는 O(n log n) 이라 통과한다냥. 숨겨진 큰 입력이 이걸 가른다냥.

합이 20억까지 갈 수 있다냥. 파이썬은 큰 정수를 알아서 다루지만, 다른 언어면 long/int64 를 쓰자냥.

미션 4합이 S 이상인 최소 길이20분

합이 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
print(0 if best == n + 1 else best)

오른쪽으로 창을 넓히다가 합이 S 이상이 되면, 왼쪽을 줄이며 더 짧게 만들 수 있는지 본다냥.

값이 전부 양수라서 이게 된다냥.

양수면 창을 넓히면 합이 커지고 줄이면 작아진다냥. 이 단조로움 덕에 왼쪽을 한 방향으로만 밀어도 된다냥.

이중 반복문으로 짜면 S 가 큰 숨겨진 입력에서 시간 초과라냥. 슬라이딩 윈도우는 O(n) 이라 통과한다냥.

확인그런 구간이 없으면 0 이라냥

전체를 다 더해도 S 에 못 미치면 0 이라냥. best 를 n + 1 같은 "불가능한 값"으로 시작해서, 끝까지 안 바뀌면 0 을 출력하자냥.

공개된 예시 5 100 → 0 으로 확인하자냥.

미션 5합이 K인 부분 배열25분

합이 정확히 K 인 연속 구간의 개수를 센다냥. 음수가 섞여 있다냥.

문제 풀러 가기

4번의 슬라이딩 윈도우를 그대로 쓰면 틀린다냥.

이 문제는 음수가 있어서 창이 단조롭지 않다냥. 넓혔는데 합이 줄어들 수 있고, 줄였다가 다시 늘려야 할 수도 있다냥. 투 포인터로는 못 잡는다냥.

공개된 예시에 -1 이 들어 있는 게 그 신호라냥. 윈도우로 짜면 여기서 바로 틀린다냥.

뼈대누적합 + 딕셔너리라냥

from collections import defaultdict

seen = defaultdict(int)
seen[0] = 1
pre = 0
cnt = 0
for v in a:
    pre += v
    cnt += seen[pre - K]
    seen[pre] += 1
print(cnt)

누적합 pre 를 딕셔너리에 세어두고, pre - K 가 몇 번 나왔는지 세면 여기서 끝나는 합 K 짜리 구간의 개수라냥.

seen[0] = 1 로 시작하는 게 중요하다냥.

"아무것도 안 더한 상태"의 누적합 0 을 하나 세어두는 거라냥. 이게 없으면 맨 앞에서 시작하는 구간을 놓친다냥. 공개된 예시 4 0 / 1 -1 1 -1 → 4 로 확인하자냥.

다섯 개 다 풀었냥? 오늘 배운 누적합과 투 포인터는 배열 문제의 기본 무기라냥. "이중 반복문이면 시간 초과인데" 싶을 때 제일 먼저 떠올리자냥.

그리고 4번과 5번의 차이 — 양수면 윈도우, 음수면 누적합 — 을 기억하면 절반은 챙긴 거라냥.

다음은 트리라냥. 사이클이 없고 하나로 이어진 특별한 그래프를 훑으며 부모·깊이·크기를 구해본다냥. 정말 수고했다냥~

직접 풀어보자! 누적합과 투 포인터 5문제

안녕, 나 코딩냥이다냥! 오늘 문제는 이중 반복문으로 짜면 시간 초과가 나도록 크게 잡아뒀다냥. 그러니 배운 무기를 꼭 써야 한다냥.

풀기 전에 정하자냥 — 누적합이냥, 투 포인터냥, 슬라이딩 윈도우냥?

어떤 무기를 고를지

"구간의 합을 여러 번 묻는다" → 누적합
"정렬된 배열에서 두 수" → 투 포인터
"양수 배열에서 조건을 만족하는 구간" → 슬라이딩 윈도우
"음수가 섞였다" → 누적합 + 딕셔너리

미션 1구간 합 구하기15분

질의마다 l번째부터 r번째까지의 합을 구한다냥.

문제 풀러 가기

뼈대한 번 더해두고, 질의마다 뺄셈 하나라냥

pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] + nums[i]

# 질의 (l, r) 마다
print(pre[r] - pre[l - 1])

질의가 많으니 매번 더하면 시간 초과라냥. 누적합은 질의마다 뺄셈 하나라냥.

pre[l - 1] 이라냥. pre[l] 이 아니라냥.

l번째 원소를 포함해야 하니 그 앞까지의 누적합을 빼야 한다냥. 한 칸 어긋나면 모든 질의가 틀린다냥. 공개된 예시 1 3 → 6 으로 바로 확인하자냥.

입력이 크니 input() 을 반복 호출하면 느리다냥. 파이썬이면 sys.stdin 으로 한 번에 읽자냥.

import sys
data = sys.stdin.buffer.read().split()

미션 22차원 구간 합20분

질의마다 직사각형 안의 수의 합을 구한다냥.

문제 풀러 가기

뼈대누적합 격자를 만든다냥

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][c] 는 (1,1) 부터 (r,c) 까지의 합이라냥.

직사각형 합의 부호를 조심하자냥.

ans = (pre[r2][c2] - pre[r1-1][c2]
       - pre[r2][c1-1] + pre[r1-1][c1-1])

위 띠와 왼쪽 띠를 빼면 왼쪽 위 모서리가 두 번 빠진다냥. 그래서 마지막에 한 번 더해준다냥. 부호를 틀리면 공개된 첫 예시부터 틀린다냥.

미션 3두 수의 합20분

합이 정확히 k 가 되는 쌍의 개수를 센다냥.

문제 풀러 가기

뼈대정렬하고 양쪽 끝에서 좁혀온다냥

a.sort()
lo, hi, cnt = 0, n - 1, 0
while lo < hi:
    s = a[lo] + a[hi]
    if s == k:
        cnt += 1
        lo += 1
        hi -= 1
    elif s < k:
        lo += 1
    else:
        hi -= 1

합이 작으면 왼쪽을 키우고, 크면 오른쪽을 줄인다냥. 값이 서로 달라서 중복 세기 걱정이 없다냥.

이중 반복문으로 짜면 시간 초과라냥.

n 이 만 개라 O(n²) 는 1억 번이라냥. 정렬 후 투 포인터는 O(n log n) 이라 통과한다냥. 숨겨진 큰 입력이 이걸 가른다냥.

합이 20억까지 갈 수 있다냥. 파이썬은 큰 정수를 알아서 다루지만, 다른 언어면 long/int64 를 쓰자냥.

미션 4합이 S 이상인 최소 길이20분

합이 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
print(0 if best == n + 1 else best)

오른쪽으로 창을 넓히다가 합이 S 이상이 되면, 왼쪽을 줄이며 더 짧게 만들 수 있는지 본다냥.

값이 전부 양수라서 이게 된다냥.

양수면 창을 넓히면 합이 커지고 줄이면 작아진다냥. 이 단조로움 덕에 왼쪽을 한 방향으로만 밀어도 된다냥.

이중 반복문으로 짜면 S 가 큰 숨겨진 입력에서 시간 초과라냥. 슬라이딩 윈도우는 O(n) 이라 통과한다냥.

확인그런 구간이 없으면 0 이라냥

전체를 다 더해도 S 에 못 미치면 0 이라냥. best 를 n + 1 같은 "불가능한 값"으로 시작해서, 끝까지 안 바뀌면 0 을 출력하자냥.

공개된 예시 5 100 → 0 으로 확인하자냥.

미션 5합이 K인 부분 배열25분

합이 정확히 K 인 연속 구간의 개수를 센다냥. 음수가 섞여 있다냥.

문제 풀러 가기

4번의 슬라이딩 윈도우를 그대로 쓰면 틀린다냥.

이 문제는 음수가 있어서 창이 단조롭지 않다냥. 넓혔는데 합이 줄어들 수 있고, 줄였다가 다시 늘려야 할 수도 있다냥. 투 포인터로는 못 잡는다냥.

공개된 예시에 -1 이 들어 있는 게 그 신호라냥. 윈도우로 짜면 여기서 바로 틀린다냥.

뼈대누적합 + 딕셔너리라냥

from collections import defaultdict

seen = defaultdict(int)
seen[0] = 1
pre = 0
cnt = 0
for v in a:
    pre += v
    cnt += seen[pre - K]
    seen[pre] += 1
print(cnt)

누적합 pre 를 딕셔너리에 세어두고, pre - K 가 몇 번 나왔는지 세면 여기서 끝나는 합 K 짜리 구간의 개수라냥.

seen[0] = 1 로 시작하는 게 중요하다냥.

다섯 개 다 풀었냥? 오늘 배운 누적합과 투 포인터는 배열 문제의 기본 무기라냥. "이중 반복문이면 시간 초과인데" 싶을 때 제일 먼저 떠올리자냥.

그리고 4번과 5번의 차이 — 양수면 윈도우, 음수면 누적합 — 을 기억하면 절반은 챙긴 거라냥.

다음은 트리라냥. 사이클이 없고 하나로 이어진 특별한 그래프를 훑으며 부모·깊이·크기를 구해본다냥. 정말 수고했다냥~