[23-24 동계 모각코] 6회차 결과

백준 11659 - 구간 합 구하기 4

문제

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

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

제한

1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N

 

예제 입력 1

5 3
5 4 3 2 1
1 3
2 4
5 5

 

 

예제 출력 1 

12
9
1

 

 

문제링크 - https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

문제 해결을 위해 고려한 조건 + 구현 방식

 

1. 입력받는 방식

- 이 문제는 입력받은 N개의 수와 M개에 해당하는 구간들의 구간 합을 구해야하기 때문에 구간들을 튜플 형식으로 리스트에 입력받는 것이 효율적이라고 생각한다.

# 입력 받기
N, M = map(int, input().split())  # 수의 개수 N, 합을 구해야 하는 횟수 M
nums = list(map(int, input().split()))  # N개의 수
sections = []  # 구간 합을 구해야 하는 리스트

for _ in range(M):
    i, j = map(int, input().split())  # 합을 구해야 하는 구간 i와 j
    sections.append((i, j))

 

 

 

 

2. 누적합 배열 처리

- 매번 구간합을 구하는 것봐다, 처음에 N개의 수를 입력받고 나면 길이 N짜리 리스트를 생성하여, 리스트의 각 자리에 그 자리까지의 누적합을 저장한 후 각 상위 누적합에서 하위 누적합을 빼주는 방식으로 구현해야 시간초과 없이 구간합을 구할 수 있다.

# 누적 합 배열 만들기
acc_sums = [0] * (N + 1)
for i in range(1, N + 1):
    acc_sums[i] = acc_sums[i - 1] + nums[i - 1]
    
# 각 쿼리에 대해 구간 합을 계산하고 출력
for i, j in sections:
    print(acc_sums[j] - acc_sums[i - 1])

 

 

문제 리뷰

지금까지 해결했던 문제들에 비하면 상당히 쉬운 편이지만 너무 단순하게 생각하면, 시간초과를 겪을 수 있는 문제이다.

그래도 문제를 읽어보자마자 누적합을 이용해야 되겠구나 생각했고, 빠르고 쉽게 문제를 해결 할 수 있었던 것 같다.

 

누적합(Prefix sum)

일반적으로  사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우O(n^2)의 시간복잡도를 갖기 때문에 입력의 범위가 클 때 사용할 수 없다. 하지만, 누적합을 이용하면 O(N)의 시간복잡도로 해결 할 수 있다.

 

누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 주로 사용하게 된다.

 

ex) 크기가 5인 배열에서 3번 인덱스와 5번 인덱스 구간의 구간합을 구한다고 가정하면, 누적합은 arr[0~b까지의 누적합] - arr[0~a-1까지의누적합]으로 표현할 수 있다.

 

 

코드 설명

# 누적 합 배열 만들기
acc_sums = [0] * (N + 1)
for i in range(1, N + 1):
    acc_sums[i] = acc_sums[i - 1] + nums[i - 1]

# 각 쿼리에 대해 구간 합을 계산하고 출력
for i, j in sections:
    print(acc_sums[j] - acc_sums[i - 1])

 

해당 문제를 해결하기 위한 누적합 배열을 만들고, 각 구간에 대한 합을 계산하기 출력하는 코드이다.

 

누적 합 배열값을 0으로 초기화 한 후에 각 1 부터 N까지 수 배열에서 입력 받은 값과 누적해서 acc_sums 배열에 추가 된 값 더해 차례로 추가해준다.

 

상위 누적합에서 하위 누적합을 빼서 구간합을 구해 출력한다.

 

 

전체 코드

import sys


def main():
    # 입력 받기
    N, M = map(int, input().split())  # 수의 개수 N, 합을 구해야 하는 횟수 M
    nums = list(map(int, input().split()))  # N개의 수
    sections = []  # 구간 합을 구해야 하는 리스트

    for _ in range(M):
        i, j = map(int, input().split())  # 합을 구해야 하는 구간 i와 j
        sections.append((i, j))

    # 누적 합 배열 만들기
    acc_sums = [0] * (N + 1)
    for i in range(1, N + 1):
        acc_sums[i] = acc_sums[i - 1] + nums[i - 1]

    # 각 쿼리에 대해 구간 합을 계산하고 출력
    for i, j in sections:
        print(acc_sums[j] - acc_sums[i - 1])


if __name__ == "__main__":
    main()

---

# 누적합 배열을 이용하면 쉽게 풀 수 있는 문제였다. 따로 특별히 더 공부하거나 할 부분은 많지 않았던 것 같고, 이번 문제는 빠르게 판단하고 빨리 코드를 작성하는 연습이 된 것 같았다. 지금까지 풀었던 알고리즘에 비해 이해하기 쉬웠지만, 너무 쉽게만 생각하지 말고 반복 숙달하면서 완전히 체득하도록 노력해야겠다는 생각이 들었다.