'부분합' 태그의 글 목록

1차원, 2차원 배열에서 구간이 주어졌을 때 어떻게 부분합을 구하는지 알아봅시다. 3차원 이상인 경우에는, 포함 배제의 원리를 알고 있어야 됩니다. 그렇기 때문에, 저는 1차, 2차원 array에서 subsum, 부분합을 구하는 것만 알려드리도록 하겠습니다. 먼저 누적합을 1차원에서 어떻게 구하는지 봅시다. 배열 arr이 있습니다. 제가 보라색으로 칠해놓은 것은 더미 데이터를 넣는데요. 0을 넣습니다. 0에 x를 더해도 0이기 때문입니다. 즉, 0은 덧셈에 대한 역원이기 때문에 보통 0으로 초기화를 합니다. nj[x]를 다음과 같이 정의합시다. 구간 [0,x]에 있는 수들의 합. 그렇다면 nj[0]의 값은 0입니다. 아무것도 없으니까 합이 0일 수 밖에 없기 때문입니다. 그러면 [0,x]까지의 합은 어떻..