[ 이것이 코딩테스트다 ] 7일차

안영우·2020년 12월 31일

동빈나 코딩테스트

[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

목록 보기

7/39

✏️ 서론

저번시간에는 투 포인터에 대해 알아보았다.
이번시간에는 구간 합 계산에 대해 알아보자.

✏️ 본론

📍 구간 합 알고리즘

Prefix_sum(구간 합): 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제

각 쿼리에 대해 구간합을 빠르게 계산하기 위해서는 N개의 수의 위치 각각에 대하여 접두사 합을 미리 구해 놓으면 된다.

여기서 접두사 합이란 리스트의 맨 앞부터 특정 위치까지의 합을 구해 놓은 것을 말한다.

예를 들어 5개의 데이터 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정해보자.
여기서 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다.
구간 합 계산 문제는 여러 개의 쿼리(Query)로 구성되는 문제 형태로 출제되는 경우가 많다.

예를 들어, M개의 쿼리가 존재한다고 가정해보자.
각 쿼리는 Right, Left로 구성되며, 이는 [Left, Right]의 구간을 의미한다.
결과적으로 쿼리가 주어졌을 때, 모든 쿼리에 대하여 구간의 합을 출력하는 문제가 전형적인 구간 합 계산문제이다.

만약, M개의 쿼리 각각, 매번 구간 합을 계산하면 이러한 알고리즘은 O(NM) 시간 복잡도를 가진다.
왜냐하면, M개의 쿼리가 수행될 때마다 전체 리스트의 구간 합을 모두 계산하라고 요구(첫 번째 수부터 N번째 수까지) 할 수 있기 때문이다.

알고리즘이 O(NM) 시간 복잡도를 가지게 되면 데이터 개수가 매우 많을 때 시간초과로 문제를 해결 할 수 없을 것이다.

항상 우리가 알고리즘을 설계할때 고려할 점 다음과 같다.

여러 번 사용될 만한 정보는 미리 구해 저장해 놓을수록 유리하다.

또, 쿼리는 M개 이지만, N개의 수는 한 번 주어진 뒤에 변경되지 않는다.
따라서, N개의 수에 대해 어떠한 처리를 수행 한 뒤에 나중에 M개의 쿼리가 각각 주어 질때마다 빠르게 구간합을 구하면 어떨까?

구간 합 알고리즘의 순서는 다음과 같다.

N개의 수에 대해 접두사 합(Prefix Sum)을 계산하여 배열 P에 저장한다.

매 M개의 쿼리 정보 [L, R]을 확인 할 때, 구간 합은 P[R] - P[L-1]이다.

만약 1~3까지의 구간 합을 구하면 P[3] - P[0] 가 된다.

만약 2~4까지의 구간 합을 구하면 P[4] - P[1]] 가 된다.

이와 같은 순서로 알고리즘을 처리하면 P[R] - P[L-1]식만 가지고도 문제를 해결 할 수 있다.
따라서 매 쿼리당 계산 시간은 O(1)이 된다. 결과적으로 모두 계산하는 작업은 O(N+M)의 시간복잡도를 가진다.

n = 5
data = [10, 20, 30, 40, 50]

value_sum = 0
prefix_sum = [0]

for i in data:
    value_sum = value_sum + i
    prefix_sum.append(value_sum)

left = 3
right = 4
result = prefix_sum[right] - prefix_sum[left - 1]
print(result)
👉🏽 70

[ 예제 ] 백준 11659

문제

예제를 풀어봤다.
구간 합 계산파트는 구현했으나, 입력값을 어떻게 작성해야할지 몰라 헤맸다.
많은 시간 끝에 문제를 해결 할 수 있었다.
sys.stdin.readline().split()의 응용법도 깨달았다.

input()으로 변수를 입력 받는다.

for()문을 작성해 input()으로 입력받은 만큼만 data_input을 생성한다.
예) input()이 5면 data_input도 4개의 리스트([10, 20, 30, 40, 50]) 선언

구간 설정값은 left, right 값으로 빼내서 계산

import sys

n, m = map(int, input().split())
data_input = list(map(int, sys.stdin.readline().split()))

value = 0
prefix_sum = [0]

for i in data_input:
    value = value + i
    prefix_sum.append(value)

for i in range(m):
    left, right = map(int, sys.stdin.readline().split())
    result = prefix_sum[right] - prefix_sum[left - 1]
    print(result)