1. 누적 합 알고리즘 정의 누적 합 혹은 부분 합 알고리즘은 말 그대로 구하고자 하는 구간의 누적된 합을 구하는 것이다. 예를 들어, 배열의 i ~ j 까지의 합을 구하고자 할 때 하나씩 더해가는 방식을 사용하는 경우에 최악의 경우 O(n^2) 시간복잡도가 생기기 때문에 메모리 낭비 혹은 시간이 오래 걸리는 문제가 발생한다. 이 문제를 해결 하기 위해서는 누적된 합을 구해 필요한 부분만 사용하고, O(N), O(1) 시간까지 단축시킬 수 있다. 2. 1차원 배열 인덱스 0 1 2 3 4 배열 10 20 30 40 50 누적 합 10 30 60 100 150 위 배열에서 인덱스 2번~4번 구간의 합을 구한다고 해보자. 4번 인덱스의 누적 합은 150(0번째~4번째 합)이다. 그러나 우리는 인덱스 2번부터..
