시작 👊

구간의 합

p.41

아 아직 41페이지네 이렇게 되면 난 굶을 수 밖에 없어.

구간 합은 합 배열을 이용해 시간 복잡도를 "더" 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다.
코딩테스트에서 사용빈도가 높으니 꼭 알아두기 바랍니다.

네!

구간 합의 핵심 이론

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야합니다. list A 가 있을 때 합 배열 S 는

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]
# A[0] 부터 A[i] 까지의 합

합 배열 은 기존의 list 데이터를 전처리한 배열이라 생각하면 됩니다. 이렇게 합 배열을 미리 구해놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N) 에서 O(1)로 감소합니다.

이렇게 구현된 합배열을 이용하면 구간의 합 역시 쉽게 구할 수 있씁니다. i ~ j 구간의 합을 구하는 것은 S[j] - S[i-1] 로 쉽게 구할 수 있습니다.

합 배열만 미리 구해두면 구간 합은 한 번의 계산으로 구할 수 있는 것입니다.
합 배열과 구간 합 공식을 적재적소에 활용하면 코딩 테스트에서 시간 복잡도를 줄이는 데 많은 도움이 될 것입니다.

감사합니다. 제가 이해한 것이 맞나 싶습니다. 일단 문제를 풀어보시져.

👨‍💻문제

백준 11659

구간 합 구하기 1

백준의 제목은 구간 합 구하기 4 네.

수 N 개가 주어졌을 때 i 번째 에서 수 j 번째 수까지의 합을 구하는 프로그램을 작성하시오.

매우 기본적인 문제인 것 같다.

입력

1번째 줄에 수의 개수 N, 합을 구해야하는 횟수 M
2번째 줄에 N 개의 수가 주어진다.
3 번째 줄 부터는 M 개의 줄에 합을 구해야하는 구간 i와 j 가 주어진다.

뭔소린지 모르겠네.

아하 이해함.

sudo를 짜보자

# 1. 첫 줄 input 에서 split 으로 N, M 구분하고.
# 2. 두 번째 줄에서 배열을 입력받아서
# 3. 세 번째 줄에서 i 와 j 를 split 으로 입력받고

N, M = map(int, input().split())
list = list(map(int, input().split()))

엥? 세번째줄부터 어떻게 해?
몇개나 받을 줄 알고?

4. map? 을 이용해서 하나씩 sum 해볼까

문제에서 수의 개수와, 합을 구해야하는 횟수는 최대 100,000 입니다. 게다가 구간마다 합을 매번 계산하면 0.5 초안에 모든 구간 합 계산을 끝낼 수 없습니다.

아?

이럴 때 바로 구간 합을 이용해야합니다!

!! 감사합니다.

근데 세번 째 줄 부터는 어떻게 하나요!

풀이 좀 보겠습니다.

아하! 나중에 for 문에서 입력받는 구나.

풀이

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
prefix_sum = [0]

tmp = 0
for i in numbers:
    tmp = tmp + i
    prefix_sum.append(tmp)

for i in range(M):
    startNum, endNum = map(int, input().split())
    answer = prefix_sum[endNum] - prefix_sum[startNum-1]
    print(answer)

import sys input = sys.stdin.readline 를 안 하면 한줄씩 읽지 않는다.

N M 을 첫 줄에서 받아 넣고, numbers 를 두 번째 줄에서 list 로 받고. 계산하다가 for 문을 M 번 돌리면서 인덱스 값을 startNum endNum 에 넣어준다.

for 문을 돌리면서 인덱스 값을 넣는다는 걸 나는 생각도 못했는데... 열심히 해야겠다.

끝