[누적합] 알고리즘 - 누적합(Prefix Sum)

누적합

구간의 누적합을 구하는 문제이다.
배열의 각 원소까지의 누적 합을 미리 계산해 놓은 배열을 생성하는 기법이다.

 

장점

• 배열 특정가간의 합을 빠르게 계산할 수 있다.

 

이론

• 구간 합 알고리즘을 활용하려면 우선 누적 합 배열을 구해야 한다. 
• 0번 인덱스에는 0을 저장하고 1번 인덱스 부터 배열을 담아야 한다.
• 누적 합 배열 arr를 구할 때 아래와 같이 구한다.

// 1차원 배열
arr[i] = arr[i-1] + inputArr[i]

// 2차원 배열
arr[i][j] = inputArr[i][j] + arr[i-1][j] + arr[i][j-1] + arr[i-1][j-1]

• 누적 합 배열 arr를 이용해 구간 합을 구하자고 할때에는 아래와 같이 구한다.

// 1차원 배열
arr[end] - arr[start-1] // start 에서 end까지의 구간 합

// 2차원 배열
arr[x2][y2] - arr[x1-1][y2] - arr[x2][y2-1] + arr[x1-1][y1-1] // x1,y1에서 x2,y2까지의 구간합

 

시간 복잡도

•  O(N)
• 입력 배열을 한번 순회해야 한다. 순회하는데 필요한 시간이 배열의 크기에 비례하므로 O(N)이 나온다.

 

누적합 문제

https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

 

풀이

https://h-castle.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-2022-KAKAO-BLIND-RECRUITMENT-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC-by-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python-%EB%88%84%EC%A0%81%ED%95%A9

[프로그래머스] 2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물 by 파이썬 (Python) :누적합