반응형
구간 합(Interval)
1.1 구간 합 문제 설명
- 구간 합 문제 : 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제
- 예를들어 5개의 데이터로 구성된 수열 10,20,30,40,50 이 있다고 가정
- 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40 = 90
- N개의 정수로 구성된 수열
- M개의 쿼리 정보가 주어진다
- 각 쿼리는 Left와 Right로 구성
- 각 쿼리에 대하여 left, right 구간에 포함된 데이터들의 합을 출력
- 수행시간 제한은 O(N+M)
1.2 구간 합 빠르게 계산하기
- 접두사 합(Prefix Sum): 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것
- 접두사 합을 활용한 알고리즘은 다음과 같다
- N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장
- 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left-1]이다
1.3 구간 합 구현
# 데이터의 개수 N과 데이터 입력받기
n = 5
data = [10, 20, 30, 40, 50]
# 접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
sum_value += i
prefix_sum.append(sum_value)
# 구간 합 계산(세 번째 수부터 네 번째 수까지)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])
반응형
'Algorithm' 카테고리의 다른 글
[Algorithm] 2019 KAKAO 개발자 겨울 인턴쉽 - 크레인 뽑기(문제 설명 및 문제 풀이) (0) | 2021.01.20 |
---|---|
[Algorithm] 2019 KAKAO BLIND RECRUITMENT - 실패율 (문제 설명 및 문제 풀이) (0) | 2021.01.18 |
[Algorithm] 39강 : 투 포인터(Two Pointers) 알고리즘의 정의와 구현 (0) | 2020.12.01 |
[Algorithm] 38강 : 에라토스테네스의 체 알고리즘의 정의와 구현 (0) | 2020.12.01 |
[Algorithm] 37강 : 소수 판별 알고리즘의 정의와 구현 (0) | 2020.11.27 |