[Algorithm] - 부분합

부분 합

---

부분 합이란?

흔히 부분합 알고리즘은 시작점 S 부터 끝점 E까지의 모든 합을 구하는 문제입니다. 하지만, 주어진 시간내에 주어지는 모든 범위의 부분합을 구하기 위해선, 일일이 다 더해주는 것은 비효율적인 일입니다.

 

• 임의의 배열을 만들어, 일일히 더하는 것이 아닌 모든 동작을 한번에 하도록 처리하여 주는 것이 주요 목표입니다.
• O(N) -> O(1)

 

아이디어

• index 2~4까지의 값을 구하려고 합니다.
• 이 때 부분합은 arr[2]+arr[3]+arr[4]라고 할 수도 있지만, sum[5]-sum[2]와도 같습니다.

 

• 만약 부분적으로 특정 값을 빼고 넣어준다고 하여 봅시다.
• [4,4,4,4,4] 라는 배열에서 1부터 마지막 index까지 6을 추가
• 2부터 3까지 index만 5를 추가한다고 해봅시다.
• 시작점은 값을 추가 마지막+1점은 값을 빼어줍니다.
• temp = [ 0,6,0,0,0,-6 ]
• temp = [ 0,6,5,0,-5,-6] 과 같은 순서가 차례대로 발생합니다.
• 앞에서 부터 반영시켜준다면[0,6,11,11,6,0]
• board에 temp 값을 더해 준다면 우리가 생각한 값과 동일하게 나오는 것을 알 수 있습니다.

 

그렇다면 2차원일 때는 어떻게 해야 할까요?

2차원

• 동작원리는 1차원가 동일합니다.
• 1,1부터 3,3까지의 부분합을 구한다고 해봅시다.
• 3,3까지의 부분합에서 1,1부터 1,3까지의 부분합 / 1,1부터 3,1까지의 부분합을 뺀 것에서 중복으로 빠진 1,1을 더하여 주면 됩니다.

즉 x1,y1,x2,y2가 있을 때 sum[x2+1][y2+1] - sum[x2+1][y1] - sum[x1][y2+1] + sum[x1][y1]

 

아래는 참고 문제 및 풀이 입니다.

https://dortmoot.tistory.com/178

[프로그래머스] - 파괴되지 않은 건물