누적 합 알고리즘에 대해 알아보자 누적 합 알고리즘 말 그대로 구간의 누적 합을 구하는 것 정확히는 "수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적 합" 예를 들자면 arr[] = { 1, 2, 3, 4, 5} 가 있다면 arr[0] ~ arr[2] 까지의 누적 합은 1 + 2 + 3 = 6 이다. 이 방법은 구간이 작으면 딱히 상관없지만 구간이 100000씩 된다면 그만큼 하나하나 더해줘야 하기 때문에 시간적 소요가 많이 든다. 그렇다면 누적합 알고리즘을 적용하면 어떻게 되느냐 배열에 저장을 할 때 합을 해서 더하면 된다 arr[] = {1, 3, 6, 10, 15} 이런식으로 1번째 부터 3번째 까지의 구간합은 arr[3] - arr[1-1] 과 같다. 이것에 대해 좋은 문제가 하..
