구간합1 누적합(Prefix Sum) 해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~ 1. 서론 알고리즘 문제를 풀다보면, 종종 배열이 주어지고, 배열 요소의 합을 구하는 문제가 나온다. 예를 들어 크기가 5인 배열에서 3번 index와 5번 index 구간의 구간합을 구하는 문제이다. 이 경우 배열의 크기가 작기 때문에 반복문을 이용해도 충분히 주어진 시간내로 풀 수 있지만, 배열이 길어질 수록 불리해진다. 왜냐하면, 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간 복잡도를 갖기 때문에 입력의 범위가 클때 사용할 수 없기 때문이다. 이럴 때 사용할 수 있는 것이 바로 누적합(Prefix Sum)이다. 누적합(Prefix Sum)방식을 .. 2023. 8. 3. 이전 1 다음
