직전 포스팅에 다 작성하기엔 양이 많아 1, 2로 나눴다. 구간 합 구간 합 문제는 리스트 내 특정 구간의 모든 수를 합한 값을 구하는 문제이다. 여러 개의 쿼리로 구성되는 문제 형태로 출제되는데, 보통 다수의 구간에 대한 각각의 합을 구하도록 요구된다. 10, 20, 30, 40, 50 리스트가 있을 때 두 번째 수부터 세 번째 수까지의 합은 50, 두 번째부터 네 번째 수까지의 합은 90이다. N개의 수와 M개의 쿼리가 주어져 각각의 구간 합을 매번 구한다면 O(NM) 의 시간복잡도를 가진다. 그렇기 때문에 데이터가 많아질 경우 해결할 수 없을 것이다. 따라서 prefix sum 기법을 이요하면 된다. 접두사 합이란 리스트 맨 앞부터 특정 위치까지의 합을 구해 놓은 것을 의미한다. 이를 이용하면 시간..
