알고리듬 - 구간 합

구간 합

구간 합은 배열, 리스트 등의 인자를 더한 결과를 저장한 것으로 시간복잡도를 줄이기 위해 활용한다.

예를 들어 아래 그림과 같이 배열 A가 있다면 순서대로 값을 더한 배열 S를 구해 문제를 푸는 것이다.

 

아래는 구간 합을 이용하는 간단한 문제 중 하나이다.

 

백준: 구간 합 구하기 4
https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

해당 문제는 간단히 값을 받을 때마다 for문을 이용해 풀 수는 있지만 시간 초과로 통과가 되지 않는다.

이를 해결하기 위해 미리 배열 S를 만든 후 뺄셈만 하여 푸는 것이다.

 

구간 합을 구현하는 것은 쉽기 때문에 문제를 보고 구간 합을 떠올리는 것이 관건이라고 생각한다.