🦠✨Cell Algorithm : 구간의 합

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

• 구간 합의 핵심
  1. 합 배열은 기존의 배열을 전처리(가공)한 배열이라 생각하면 된다.
     • ex) [1, 2, 3, 4, 5] - (합 배열) -> [1, 3, 6, 10, 15]
     • ex) [1, 2, 3, 4, 5] - (구간의 합/2~4까지) -> 3+4+5 = 12
  2. 시간 복잡도는 O(N)이다.
  3. 합 배열과 구간 합 공식을 전재적소에 활용하면 코딩 테스트에서 시간 복잡도를 줄이는 데 많은 도움이 될 것이다.
  4. 꼭 원리를 이해해야한다.

---

* 누적의 합

구간의 합관련 문제들을 실버 3~1정도이다. 따라서 누적의 합 예시를 봐야 조금 더 이해가 될 것이다. O(N)인 누적의 합을 하기 이전에 아래는 O(N^2)의 시간 복잡도인 코드를 먼저 살펴 보겠다.

 

array = [1, 8, 7, 4, 3, 5, 6]

# n = len(array)

prefix_sum = [0] * len(array)

for i in range(len(array)):

  print()

  for j in range(i+1):

    print(f'{j}',end=' ')

    prefix_sum[i] += array[j]

print()

print(prefix_sum)

0 
0 1 
0 1 2 
0 1 2 3 
0 1 2 3 4 
0 1 2 3 4 5 
0 1 2 3 4 5 6 
[1, 9, 16, 20, 23, 28, 34]

 

코드를 살펴보면  이중 for문으로 되어 있고 prefix_sum배열 변수는 누적되는 배열을 담아내는 변수이다. 이제 O(N)으로 되어 있는 코드를 살펴보면 아래와 같다.

 

array = [1, 8, 7, 4, 3, 5, 6]

# n = len(array)

prefix_sum = [0] * (len(array) + 1)

print(f'{prefix_sum}')

 

for i in range(len(array)):

  print(f'{i}',end=' ')

  prefix_sum[i + 1] = prefix_sum[i] + array[i]

  print(prefix_sum)

print()

print(prefix_sum)

 

[0, 0, 0, 0, 0, 0, 0, 0]
0 [0, 1, 0, 0, 0, 0, 0, 0]
1 [0, 1, 9, 0, 0, 0, 0, 0]
2 [0, 1, 9, 16, 0, 0, 0, 0]
3 [0, 1, 9, 16, 20, 0, 0, 0]
4 [0, 1, 9, 16, 20, 23, 0, 0]
5 [0, 1, 9, 16, 20, 23, 28, 0]
6 [0, 1, 9, 16, 20, 23, 28, 34]

[0, 1, 9, 16, 20, 23, 28, 34]

 

preifx_sum 배열 변수의 크기를 미리 +1을 해놓은 상태에서 index 0자리 뒤에서 부터 누적의 배열을 실행한다. 이러한 개념을 잘 생각하면서 구간의 합을 보면 수월할 것이다.

---

* 구간의 합

구간의 합을 이해하기 위해서 간단한 예시로 설명을 해보겠다. 배열이 [1,2,3,4,5]가 있다. 여기서 구간이 3이라면 3구간 만큼의 값을 활용하면 되는 것이다. 즉, 구간의 합을 구하는 구간이 3이면 먼저 1,2,3까지의 3구간의 합을 구하면 된다. 따라서 1+2+3인 6이 나오는 것이다. 이후에 2,3,4의 구간의 합을 구한다면 단순히 우리 사람의 머리로는 2,3,4를 더하면 되겠지만 컴퓨터 기준으론 메모리 효율적으로 2,3,4라는 공간을 또 다시 만들기 보다 1+2+3에서 4를 더하고 기존에 있는 1을 빼면 되는 것이다. 따라서 1+2+3+4-1의 과정을 거치면 되는 것이다. 이를 코드를 통해서 살펴보면 아래와 같다.

index 1에서부터 5까지의 구간의 합을 출력하면 된다.

 

array = [1, 8, 7, 4, 3, 5, 6]

n = len(array)

prefix_sum = [0] * (n + 1)

x, y = 1, 5

for i in range(n):

print(f'{prefix_sum[i]} + {array[i]}')

prefix_sum[i + 1] = prefix_sum[i] + array[i]

print(prefix_sum)

 

part_sum = prefix_sum[y] - prefix_sum[x - 1]

print(part_sum)

 

0 + 1
[0, 1, 0, 0, 0, 0, 0, 0]
1 + 8
[0, 1, 9, 0, 0, 0, 0, 0]
9 + 7
[0, 1, 9, 16, 0, 0, 0, 0]
16 + 4
[0, 1, 9, 16, 20, 0, 0, 0]
20 + 3
[0, 1, 9, 16, 20, 23, 0, 0]
23 + 5
[0, 1, 9, 16, 20, 23, 28, 0]
28 + 6
[0, 1, 9, 16, 20, 23, 28, 34]
23

 

왜 빼기를 해야하는 지 더 명확한 증명이 필요하다.

강의 이미지 첨부

[알고리즘 이론] 구간합, 누적합(prefix sum)

---

 

누적의 합과 구간의 합 차이는 무엇인가.

결과적으론 같은 결과를 보여준다. 그렇다면 이 둘의 명확한 차이는 무엇일까?

---

만약 계속해서 배열의 값이 변한다면 어떻게 해야할까?

이럴때는 세그먼트 트리/인덱스 트리를 사용해야한다.

---

실전 문제 : [BOJ] 11660

* 시간 복잡도를 어떻게 줄일 수 있는지 고민 할 것.

나머진 연산을 하고 값들을 더하고 다시 3을 나누는 것과 해당 범위의 값을 더하고 3을 나누는 결과는 같다는  것이다.