EC.CREW 2기 5주차

 

5주차 주제 : <자료 구조 - 구간 합>

 

1. 구간 합 vs 부분 합

 

- 부분 합 : 0 ~ a 까지의 합 ( 처음부터 끝까지 )

- 구간 합 : a ~ b 의 합 ( 일정 구간의 합 )

 

 

2. 구간 합 알고리즘

 

num = [ 1, 2, 3, 4, 5 ] 에서 num[a] ~ num [b]의 합을 구할 때

 - sum[i] = num[0] + num[1] + ...+num[i-1]을 만족시키는 sum을 구한다

    sum = [ 0, 1, 3, 6, 10, 15 ]

- num[a] ~ num[b]의 합은 sum[b+1] - sum[a]를 통해 구할 수 있다

   ex) num[2] ~ num[4] 의 합 = sum[5] - sum[2]

         num[2] + num[3] + num[4] = (num[0]+num[1]+num[2]+num[3]+num[4]) - (num[0]+num[1])

         3 + 4 + 5 = 15 - 3

 

 

 

3. 활용 문제

 

# 1 구간 합 구하기 4

 

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

11659번: 구간 합 구하기 4

 

 

 

 

 

N,M = map(int,input().split())
num = list(map(int, input().split()))
sumList = []
p_sumList = []

sum = 0
for a in range(int(N)):
    sum+=num[a]
    sumList.append(sum)

for k in range(M):
    i, j = map(int, input().split())
    if i == 1:
        p_sumList.append(sumList[j-1])
    else:
        p_sumList.append(sumList[j-1] - sumList[i-2])

for b in range(len(p_sumList)):
	print(p_sumList[b])

 

 

 

# 2 구간 합 구하기 5

 

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

11660번: 구간 합 구하기 5

 

 

  어떻게 풀 지 대충 머릿속으로는 그려지는데 코드를 어떻게 짜야할 지 감이 안 잡힌다...

  조금만 더 머리 굴리면 될 것 같은데...!! 

 

 

 

 

# 3 나머지 합

 

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

10986번: 나머지 합

 

이 문제는 사실 이해하는 데에도 시간이 오래 걸렸다

나중에 재도전...!!

 

 

 

 

 

문제의 난이도가 올라갈수록 예전처럼 알고리즘 따위 생각 안 하고 다중 for문을 써대면서 문제를 푸니까 시간 초과 에러가 나온다.

슬슬 알고리즘을 공부해봐야겠다.