C++ 누적합

알고리즘 문제를 풀다보면 종종 for 문 대신 '누적합'을 사용해야하는 문제가 나온다 누적합이란? - 요소들이 누적된 합으로, 어떤 배열을 기반으로 요소들의 누적된 합을 저장해 새로 배열을 만들어 이를 활용하는 방법 - 앞에서 더하는 prefix sum (주로 코딩테스트에서는 prefix sum만 나옴!!) - 뒤에서 더하는 suffix sum prefix sum 만들 때 주의해야 할 점 - 0번째 요소는 비워두고 1번째 요소부터 사용하자 psum[1] -> 0, 1 psum[2] -> 0,1,2 psum[3] -> 0, 1,2,3 psum[4] -> 0,1,2,3,4 누적합을 코드로 구현해보자! for(int i = 1; i > a[i]; psum[i] = psum[i-1] + a[i]; } for(i..

2023.02.10