개발새발 로그

누적합(prefix sum) 본문

알고리즘

누적합(prefix sum)

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

 

 

728x90
반응형
LIST
저작자표시

'알고리즘' 카테고리의 다른 글

다이나믹 프로그래밍(Dynamic Programming) - 타일링 문제  (0) 2023.05.31
다이나믹 프로그래밍(Dynamic Programming) - 메모제이션  (0) 2023.05.31
그래프 이론 (이진트리의 구현과 순회방식)  (0) 2023.05.31
그래프 이론(크루스칼 알고리즘)  (0) 2023.05.31
그래프이론(서로소집합)  (0) 2023.05.31
'알고리즘' Related Articles more