[알고리즘 코딩테스트](2)자료구조-2: 구간 합

구간 합

: 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 => 합 배열을 구해야 함

 

합 배열

: 기존의 리스트 데이터를 전처리한 배열 =>기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소

S[i] =A[0]+A[1]+A[2]+A[3]....+A[i-1]+A[i]
S[i]=S[i-1]+A[i]

배열의 i번째부터 j번째까지의 구간 합을 구하는 공식

S[j]-S[i]

 

문제 1

1번째 줄에 수의 개수 N(1<=N<=100,000), 합을 구해야 하는 횟수 M(1<=M<=100,000), 2번쨰 줄에 N개의 수가 주어진다. 각 수는 1,000보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야하는 구간 i와 j가 주어진다.

 

입력 예제

5,3

5,4,3,2,1

1 3

2 4

5 5

 

코드 작성하기

import sys
input =sys.stdin.readline
suNo, quizNo = map(int,input().split())
numbers=list(map(int,input().split()))
prefix_sum =[0]
temp=0

for i in numbers:
     temp=temp+i
     prefix_sum.append(temp) //합 배열 만들기

for i in range(quizNo):
     s,e = map(int,input().split())
     print(prefix_sum[e]-prefix_sum[s-1])) //합 배열에서 구간 합 구하기

역시나 코드 자체는 그다지 어렵지 않지만, 파이썬으로 코테를 준비하다보니 어제와 마찬가지로 입력을 받는 부분이 낮설게 느껴졌다.

1. sys.stdin.readline

https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

[Python 문법] 파이썬 입력 받기(sys.stdin.readline)

한줄을 입력 받는 것이 아니라, 여러 줄을 입력받아야 할 때에 사용하는 모듈로 한 줄 단위로 입력을 받을 수 있게 한다.

입력 예시의 경우 위 코드에서 suNo에는 5, quizNo에는 3, 그리고 numbers에는 [5,4,3,2,1] prefix_sum에는 [5,9,12,14,15]

 

2. for i in range(순회할 횟수)

파이썬을 이용하여 반복문을 만드는 방법 중 하나로 예시 입력의 경우 3번 입력을 받아 출력을 한다.

 

 

문제 2

1번째 줄에 수의 개수 N(1<=N<=100,000), 합을 구해야 하는 횟수 M(1<=M<=100,000), 2번쨰 줄에 N개의 수가 주어진다. 각 수는 1,000보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야하는 구간 i와 j가 주어진다.