누적합 알고리즘

박세건·2023년 5월 26일
0

알고리즘

목록 보기
1/1


파괴되지 않은 건물이라는 코딩문제를 해결하는 도중에 누적합에 대해서 다시한번 알게되었고 확실하게 알기위해서 적어보기로 했다.

먼저 누적합이란,

0번째 인덱스 부터 N 번째 인덱스까지 탐색하면서 인덱스 i일때 0번째 인덱스 부터 0번째 인덱스합

예를 들어, 1,2,3,4,5 라는 배열이있다면 누적합은 1,3,6,10,15 가되는 것이다.
여기까지는 알고있었던 내용이지만 이를 이용해서 문제를 쉽게 해결할 수 있었다.

10개의 배열 0,0,0,0,0,0,0,0,0,0 이 있을때 (맨 앞을 0번째 인덱스라 하자)
1번째 인덱스부터 7번째 인덱스까지 +5를 해주고 싶다면

첫번째 방법

1번째부터 7번째까지 +5를 해주는 방법이 있다 7번의 증가를 해줘야한다.

하지만 누적합을 이용한 두번째 방법

다른 배열을 준비한다 구해야하는 배열의 크기의 +1 이 된 11개의 배열을 준비한다.
(이는 누적합을 나타내 주기 위함)
1번째부터 7번째까지의 증가이기때문에 1번째와 8번째(7+1) 번째에 마킹을 해준다
0,5,0,0,0,0,0,-5,0,0,0 배열을 이렇게 완성이된다.
이 배열의 누적합을 구해주면 0,5,5,5,5,5,5,0,0,0,0 이 된다
이를 원래의 배열과 합쳐주면 정답을 구할 수 있는 것이다.

지금까지는 누가 봐도 두번째 방법이 복잡하고 오래 걸리는 것처럼 보인다.

하지만 증가를 시키라는 명령과 배열이 클 경우를 생각해보자!
배열의 크기가 10000개 이고 명령이 100개 일때, 이 명령은 0번째 부터 9999번째 까지 크기를 +1을 하라는 명령이고 같은 명령이 100개가 들어왔다고 하자.
그렇다면 첫번째 방법으로는 0번째부터 9999번째까지 +1을 해주는 식을 100번을 반복할 것이다.

눈으로 봤을때 10000*100=(1000000)의 시간이 걸릴것이다.

그렇다면 두번째 방법을 사용한다면, 10001개(10000+1) 크기의 배열을 만들어주고
0번째에 +1해주고 10000번째에 -1 을 100번 반복한 후에 누적합을 구해주고 원래의 배열에 더해주면 된다

이는 +1 해주고 -1 해주는 2(두번)*100=(200)의 시간이 걸린다(누적합을 구해주고 원래의 배열에 더해주는 시간은 빼고 계산한다)

1000000과 200 엄청난 차이가 발생한다 배열의 크기와 명령의 크기가 더 커진다면 어마어마한 차이가 발생할 것이다.

이처럼 해결하고자 하는 문제에 어떤 알고리즘을 사용하면 좋은 효과를 볼 수 있을지 생각 하는 습관을 기르자!

아직 어렵다면 외우자!
A~B까지 증가 or 감소 시키는 문제를 만나면 누적합을 떠올리자!!

profile
멋있는 사람 - 일단 하자

0개의 댓글