[BAEKJOON] 구간 합 구하기 4 (누적합)

 

안녕하세요! 개발감자 박그냥입니다🥔

오늘은 누적합에 대해서 정리해보도록 하겠습니다.

 

 

 

알고리즘은 공부했지만 직접 문제를 풀어보았습니다.

백준 문제 중 <구간 합 구하기 4>라는 문제입니다.

[알고리즘 마스터] 1. 누적합

1. 풀이

import sys

# n,m 입력받기
N, M = map(int, input().split())
# 리스트 입력받기    
List = list(map(int, input().split()))
prefix = [0] * N
prefix[0] = List[0] # 첫번째 값을 넣어줌
for i in range(1, N): # 두번째 값부터 누적합을 저장
    prefix[i] = prefix[i-1] + List[i]

queries = []
for k in range(M):
    # n,m 입력받기
    i, j = map(int, input().split())
    queries.append((n, m))

for query in queries:
    i, j = query
    if i == 1:
        sys.stdout.write(str(prefix[j-1]) + "\n")
    else:
        sys.stdout.write(str(prefix[j-1] - prefix[i-2]) + "\n")

인증!

2. 풀이 설명

i부터 j번까지의 합을 구하려면, 누적합을 구하는 것이 시간복잡도 측면에서 빠릅니다.

n,m와 1차원 리스트를 입력받아 저장하고, 저장한 리스트를 이용하여 누적합 배열 (prefix)를 구합니다.

i,j를 m만큼 입력받고, 이를 가지고 i부터 j번까지의 합을 구합니다.

만약 i가 1인 경우에는 누적합 합 하나만 가지고 오면 되기 때문에 따로 경우를 빼서 구현해줍니다.

i-2인 이유는 i번 부터의 합을 구하기 위해서는 파이썬 인덱스는 우리가 생각하는 인덱스에서 -1을 한 것이고, i 번째의 요소를 포함해서 더해주려면 i 앞의 누적합을 빼줘야 하기 때문에 -1이 두번 적용되어 i-2 가 됩니다.

j-1은 위에서 설명한 바와 같이 파이썬 인덱스와 우리가 생각하는 순서가 1이 차이가 나기 때문에 -1을 해줍니다.

 

3. 느낀 점

코딩테스트 준비를 위해 백준 문제를 풀라는 이야기를 많이 들었는데 이제서야 준비하게 된 게 정말 아쉽습니다.

하지만, 늦게 시작한 만큼 더 열심히 하고자 합니다! (그래도 알고리즘 푸는 건 재미있어서 다행입니다)

오늘 풀면서 입력과 출력을 번갈아면서 하려고 해서 시간초과가 결과로 나왔습니다.

무조건 입력과 출력은 따로! 한 번에 진행해야 하는 것을 배웁니다.

 

 

그럼 유익한 포스팅으로 돌아오겠습니다! 개발감자였습니다.