2차원 배열 누적 합

1. 내 생각이 막혔던 부분 첫번째

 - arr [ i ] [ j ]

 (1) 첫번째 행을 누적해서 더한다.(이 부분은 일단 맞음)

 (2) 두번째 행은.. arr [ 0 ][ j ]를 arr[ 1 ][ j ] ?에? 더하는 건데.. 바로 결괏값이 나올수가 있나?

 => 이 부분에서 막혔다. 열을 어떻게 하지?

 

일단 틀린건, arr[0][j]가 아니다. sum_list[ 0 ][ j ] 이다.

sum_list[ 0 ][ j ] = sum(arr[ 0 ][ : j ])

이렇게도 가능

sum_list[ 0 ][ j + 1 ] += arr[ 0 ][ j ]

그런데, sum_list[ 0 ][ j ]를 하게 되면, 한 칸 한 칸이, sum_list의 값이 된다. 잊어버리지 않게 표시하자면, sum_list의 1행은 다음처럼 값을 나타낼 수 있다.

arr[0][0]	arr[0][0] + arr[0][1]	arr[0][0]+arr[0][1]+arr[0][2]

sum_list 배열

 

그렇다면, 그 다음은?

2. 내가 잘못 생각한 부분 두번째

 sum_list[1][0] = arr[0][0] + arr[1][0]

 sum_list[1][1] = sum_list[0][1] + arr[0][0] + arr[1][0]

 sum_list[1][2] = sum_list[0][1] + arr[1][0] + arr[1][1]+ arr[1][2]

 

얼핏 보면 이상하진 않은데, 내가 이게 맞나? 하는 생각이 들었던 건, sum_list와 arr를 동시에 계산하는 부분 이었다.

잘못된 부분을 더 자세히 말하자면

일단 첫 행의 누적합을 구한다. 그리고 다음 행 에서는 다음행의 행 누적합과 이전 행의 이 열 까지의 누적합을 더했던 것

=> 잘못된 부분은 행 누적합+ 열 누적합을 섞어서 했던 것이 문제였다.

=> 일단 행 누적합을 모두(1행 부터 i행까지) 끝낸 뒤 열 누적합(1열 부터 j열 까지)을 진행해야 한다.

 

나는 sum_list가 완성된 누적합의 결과인 것으로 생각해 계산했는데, (결과적으로는 맞다.. 나중에 공간복잡도를 줄이기 위해 그렇게 사용되긴 하지만, 이 단계에서는 아니다.)

sum_list는 완성된 열과 행의 누적합이 아니었다. 이 단계에서 sum_list는 행의 누적합이었다.

 

sum_list[0][0]	sum_list[0][1]	sum_list[0][2]
sum_list[0][0] + sum_list[0][1]	sum_list[0][1] + sum_list[1][1]	sum_list[0][2] + sum_list[1][2]
sum_list[0][0] + sum_list[0][1] + sum_list[0][2]	sum_list[0][1] + sum_list[1][1] + sum_list[2][1]	sum_list[0][2] + sum_list[1][2] + sum_list[2][2]

result_sum_list 배열

 

추가적으로 여기서 공간복잡도를 더 늘리지 않기 위해서(result_sum_list 배열을 하나 더 만들지 않게 하기 위해)고민했다.

행의 누적합 이후 sum_list는 일단 다음 표와 같은 값이 들어가게 된다. 

sum_list[0][0]	sum_list[0][1]	sum_list[0][2]
sum_list[0][1]	sum_list[1][1]	sum_list[1][2]
sum_list[0][2]	sum_list[2][1]	sum_list[2][2]

 

3. 그런데 또 잘못 생각한 부분 세번째

result_sum_list는 결국 여기서 열 누적합이기 때문에, sum_list[ i ][ j ] = sum(sum_list[ : i ][ j ]) 로 표현할 수 있다고 생각했지만 그러면 안되고!

열 누적합은 다음처럼 차근차근 더해가는 방법으로 sum_list를 더해야 한다.

sum_list[ i + 1 ][ j ] += sum_list[ i ][ j ]

 

결론

1. 먼저! 행부터 모든 행의 누적합을 만든다. arr의 누적합

2. 열을 더한다. sum_list의 누적합