'prefix sum' 태그의 글 목록

부분합은 특정 구간의 합을 효율적으로 계산하기 위해 누적합을 활용하는 방법이다. 입력할때 전부 더해두고 이후에 재사용한다는 계념이다. 그래서 최소 한번이상 사용해야 이득이다. 1차원배열은 index = [1] [2] [3] [4] [5] [6] 이 있다 DP = [1] [3] [6] [10] [15] [21] 배열을 만들어준뒤 배열은 이전값에서 M을 더한 값 [N]= [N-1] + M 3번부터5번값 을 구해야 한다면? 아래처럼 3 부터 5까지 index를 하나씩 올리며 구해도 괜찮다. [1] [2] [3] [4] [5] [6] 1 2 3 4 5 6 ..

알고리즘 2024. 10. 29. 15:30

이전 1 다음