백준 11659 파이썬, 구간 합 알고리즘, sys.stdin.readline()

백준 11659 : 구간 합 구하기 4

문제

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

11659번

 

답안 코드 :

import sys
input = sys.stdin.readline
suNo,quizNo = map(int, input().split())
numbers = list(map(int, input().split()))
prifix_sum = [0]
temp = 0
for i in numbers:
    temp = temp + i
    prifix_sum.append(temp) #합 배열 만들기
for i in range(quizNo):
    s, e = map(int, input().split())
    print(prifix_sum[e]-prifix_sum[s-1]) #합 배열에서 구간합 구하기

 

 

생각 :

구간 합
구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.
* 코딩 테스트에서 사용 빈도가 높다!!!

구간 합의 핵심 이론
-구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.
-합 배열은 기존의 리스트 데이터를 전처리한 배열이라고 생각하자. 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.
- 합 배열 만드는 공식
S[i] = S[i - 1] + A[i]
- 위의 합 배열을 이용하여 구간 합 역시 쉽게 구하기 가능
S[j] - S[i - 1] #i에서 j까지 구간 합

11659번

# 문제에서 수의 개수와 합을 구해야 하는 횟수는 최대 100,000이다
# 게다가 구간마다 합을 매번 계산하면 1초안에 모든 구간 합 계을 끝낼 수 없다.
# 이럴 떄 구간 합을 이용!!!
# 구간 합을 매번 계산한다면 최악의 경우 1억 회 이상의 연산을 수행 따라서 1초 이상의 수행 시간이 필요.

 

# input()대신 sys.stdin.readline()을 사용하는 이유

 

# 한 두줄 입력받는 문제들과 다르게, 반복문으로 여러줄을 입력 받아야 할 때는 input()으로 입력 받는다면 시간초과가 발생할 수 있습니다. 대표적인 예시가 백준 BOJ 15552번 문제입니다.

# sys.stdin.readline()은 한줄 단위로 입력받기 때문에, 개행문자가 같이 입력 받아집니다.

출처: https://mkisos.tistory.com/entry/백준-1377-파이썬 [MK 실험실:티스토리]