목록누적합 (1)

개발새발 로그

누적합(prefix sum)

누적합은 구간의 누적합을 구하는 문제 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우O(n^2)의 시간복잡도를 갖기 때문에 입력의범위가 클 때 사용할 수 없습니다. 하지만 Prefix sum방식을 사용하면 O(N)으로 해결 할 수 있습니다 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 사용한다.
알고리즘 2023. 5. 31. 11:18
이전 Prev 1 Next 다음