배열과 구간 합

배열

배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다. 인덱스를 사용하여 값에 바로 접근할 수 있고, 새로운 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.

구간 합

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

합 배열

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 리스트 A가 있을 때 합 배열 S는 다음과 같이 정의한다.

A[0]부터 A[i] 까지의 합
S[i] = A[0] + A[1] + … + A[i-1] + A[i]

합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

A = [1, 2, 3, 4, 5]
S = [1, 3, 6, 10, 15] # [1, (1 + 2), (1 + 2 + 3), ...]

A[i]부터 A[j]까지의 리스트 합을 합 배열 없이 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우로 시간 복잡도는 O(N)이다. 이런 경우 앞에서 알아본 합 배열을 사용하면 O(1) 안에 답을 구할 수 있다. 예를 들어, A[3]까지의 합은 S[3]인 11로 바로 값을 알 수 있다.

합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]

자바스크립트로 다음과 같이 구현할 수 있다.

const A = [1, 2, 3, 4, 5];
const S = [A[0]];
for (let i = 1; i < A.length; i++) {
  S[i] = S[i - 1] + A[i];
}
console.log(S); // [1, 3, 6, 10, 15]

구간 합

이렇게 구현된 합 배열을 이용하여 구간 합 역시 쉽게 구할 수 있다.

i에서 j까지 구간 합 구하기
S[j] - S[i-1]

예를 들어, A[2]부터 A[4]까지의 구간 합을 구해야 한다.

A = [1, 2, 3, 4, 5]
S = [1, 3, 6, 10, 15]

A[0] + … + A[4] 에서 A[0] + A[1]을 빼면 구간 합 A[2] + … A[4]가 나오므로, S[4]에서 S[1]을 빼면 구간 합을 쉽게 구할 수 있다.

S[4] = A[0] + A[1] + A[2] + A[3] + A[4] // 1 + 2 + 3 + 4 + 5
S[1] = A[0] + A[1] // 1 + 2
// j = 4, i = 2
S[4] - S[1] = A[2] + A[3] + A[4] // 3 + 4 + 5

A[2] 부터 A[4]까지니 j = 4, i = 2 이다. 위 공식을 적용했을 때 S[4] - S[2 - 1], 따라서 S[4] - S[1]가 된다.

문제

다음은 구간 합을 구하는 백준 문제이다. 구간 합 구하기 4

자바스크립트로 풀었는데, 합 배열을 사용하지 않을 경우 시간 초과가 발생했다. 시간 초과가 발생했던 코드이다.

/* input
5 3
5 4 3 2 1
1 3
2 4
5 5
*/
const [_, nums, ...input] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const A = nums.split(" ").map(Number);
const result = [];

for (let l of input) {
  // 시작점과 끝점 s, e를 공백 기준으로 분리하고 숫자형으로 변환
  const [s, e] = l.split(" ").map(Number);
  // A 배열에서 s번째부터 e번째까지의 합을 구해서 result 배열에 추가
  let sum = 0;
  for (let i = s - 1; i < e; i++) {
    sum += A[i];
  }
  result.push(sum);
}
console.log(result.join("\n"));

합 배열을 이용하니 통과했다.

// A: 5 4 3 2 1
// S: [ 0, 5, 9, 12, 14, 15 ]
// 합을 구해야 하는 구간
// 1 3 -> 5 + 4 + 3 = 12, S[3] - S[0] = 12
// 2 4 -> 4 + 3 + 2 = 9, S[4] - S[1] = 9
// 5 5 -> 1, S[5] - S[4] = 1

const [_, nums, ...input] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const A = nums.split(" ").map(Number);
const S = [0];
for (let i = 0; i < A.length; i++) {
  S[i + 1] = S[i] + A[i];
}

const result = [];

for (let l of input) {
  const [i, j] = l.split(" ");
  result.push(S[j] - S[i - 1]);
}
console.log(result.join("\n"));

구간 합 응용

다음은 구간 합을 응용해서 풀어야하는 백준 10986 나머지 합 문제이다. 책에 이 문제도 소개되어 있어서 처음에 풀이를 보지 않고 도전했지만 시간 초과로 실패했다.

const [first, input] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const [N, M] = first.split(" ").map(Number);

const A = input.split(" ").map(Number);

const S = [0];
for (let i = 0; i < A.length; i++) {
  S[i + 1] = S[i] + A[i];
}

let count = 0;
for (let i = 1; i < S.length; i++) {
  for (let j = i; j < S.length; j++) {
    if ((S[j] - S[j - i]) % M === 0) {
      count++;
    }
  }
}

console.log(count);

이후 책을 봤는데 나는 수포자라서 풀이를 이해하는데 많은 시간이 걸렸다. 수학 공부 열심히 해야겠다…

const [first, input] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const [N, M] = first.split(" ").map(Number);

const A = input.split(" ").map(Number);

const S = [0];
for (let i = 0; i < A.length; i++) {
  S[i + 1] = S[i] + A[i];
}

let answer = 0;
const C = Array(M).fill(0);
for (let i = 1; i < S.length; i++) {
  let remainder = S[i] % M;
  if (remainder === 0) {
    // 0~i까지의 구간 합 자체가 0일 때 정답에 더하기
    answer += 1;
  }
  C[remainder] += 1;
}

for (let i = 0; i < M; i++) {
  if (C[i] > 1) {
    // 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하기
    answer += (C[i] * (C[i] - 1)) / 2;
  }
}

console.log(answer);

1. 합 배열을 구한다.
2. 합 배열의 각 원소를 M으로 나머지 연산하여 값을 업데이트한다.
3. 변경된 합 배열에서 원소 값이 0인 개수만 세어 정답에 더한다.
   • 변경된 합 배열의 원소 값이 0이라는 뜻은 원본 리스트의 0부터 i까지의 구간 합이 이미 M으로 나누어떨어진다는 뜻이기 때문
4. 변경된 합 배열에서 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구하기
   • 변경된 합 배열에서 원소 값이 같은 2개의 원소를 선택하면, 그 사이의 구간의 합도 M으로 떨어진다. (아래 내용 참고)

원소 값이 같은 2개 사이의 구간의 합이 왜 M으로 떨어지지?

이 부분이 제일 이해가 안 갔다. 합 배열을 구한 후 나머지 연산한 결과가 S = [1, 0, 0, 1, 0] 이라고 하면 S[0]과 S[3] 사이 구간의 합이 M으로 떨어진다고 한다. 둘 다 나머지가 1인데 어떻게 그 구간이 M으로 떨어질 수 있는 건지 궁금해서 GPT한테 물어봤다.

Q. 나머지가 1이라는건 3으로 나누어 떨어지지 않았다는건데 어떻게 그 구간의 합이 M으로 나누어 떨어질 수 있는거야? (M = 3)

A. 좋은 질문이에요! 이 부분을 더 쉽게 설명해볼게요. 나머지가 같은데 왜 차이가 3의 배수인지?

나머지의 의미 다시 보기

우선 나머지가 같다는 게 무슨 의미인지 다시 생각해볼게요. 예를 들어, 숫자 7과 10을 3으로 나눈다고 해볼까요?

• 7을 3으로 나누면 나머지가 1이죠. 7 \ 3 = 2 (몫) 나머지 1
• 10을 3으로 나누면 나머지도 1이죠. 10 \ 3 = 3 (몫) 나머지 1

두 수 모두 3으로 나눈 나머지가 1입니다. 그런데 이 두 수의 차이를 보면: 10 - 7 = 3 여기서 3은 3의 배수예요! 이처럼, 두 숫자가 3으로 나눈 나머지가 같으면, 그 두 숫자의 차이는 3의 배수가 되는 겁니다. 왜냐하면, 두 수에서 나머지 부분은 같고, 나머지 부분을 뺀 나머지 차이는 3으로 나누어떨어지는 수이기 때문이에요.

누적 합 배열에서 나머지가 같은 이유

이제 문제의 누적 합 배열로 돌아가 볼게요. S[0] 과 S[3] 이 나머지가 같다고 했죠? 이 말은 S[0] 과 S[3] 의 나머지가 같으니까 이 둘의 차이는 3의 배수라는 뜻입니다.

• S[0] 은 리스트의 처음부터 A[0] 까지 더한 값이에요.
• S[3] 은 리스트의 처음부터 A[3] 까지 더한 값이죠.

이때 S[3] - S[0] **은 A[1] + A[2] + A[3] 에 해당하는 구간의 합인데, 이 값이 3의 배수입니다. 왜냐하면 나머지가 같으니까 그 차이가 3의 배수가 되는 것이에요.

다시 설명하자면: 1. S[0] 과 S[3] 이 나머지가 같다는 것은, 이 둘의 차이가 3의 배수라는 뜻이에요. 즉, S[3] - S[0] 이 3의 배수라는 겁니다. 2. 그런데 S[3] - S[0] 는 A[1] + A[2] + A[3] 의 합이니까, 이 구간의 합이 3으로 나누어떨어진다는 거죠.

핵심 원리: 나머지가 같으면 그 둘의 차이는 M의 배수가 됩니다. 이 성질 덕분에 나머지가 같은 누적 합 배열의 두 값 사이의 구간 합이 M으로 나누어떨어지는 거예요.

---

코드를 제출해서 통과한 이후 다른 사람이 한 걸 봤는데 이보다도 훨씬 더 간단하게 풀었더라… 구간 합 자체는 이해하기 쉬운데 응용해서 풀려면 많은 연습이 필요할 것 같다. + 수학 공부도…

출처

• 알고리즘 코딩테스트 책 (이지스퍼블리싱)