누적 합 연산 - 수열

처음 문제를 보고 1차원적으로 풀이를 했었을때는 다음과 같이 작성했다.

const Answer = (N, list) => {
  let result = [];
  for (let i = 0; i < list.length - (N - 1); i++) {
    const breakPoint = i + (N - 1);
    let sum = 0;
    for (let j = i; j <= breakPoint; j++) {
      sum += list[j];
    }
    result.push(sum);
  }

  console.log(Math.max(...result));
};

list를 순회하면서 각 인자마다 N번의 계산을 하는 코드인데,

하지만 강의에서 누적합이라는 개념이 배우면서 n번이 아닌, 1번의 계산만 할 수 있는 방법을 설명해줬다.

예제 2의 경우에는 처음 코드대로라면 N이 5이므로 5번씩 덧셈을 할 것이다.

배열의 길이만큼 순회하고, 각 인자마다 N번의 연산을 할텐데, 누적합에서는

각 인자들을 순서대로 더하면 다음과 같은 배열이 나온다.

1, 2, 3, 4, .. 순서대로

a1, a1+a2, a1+a2+a3, ...의 값들의 정렬이 나온다

만약 내가 4번째 인자부터 8번째 인자까지 5개의 합을 구하고 싶다면

8번째 값에서 3번째 값을 빼주면 된다.

3번째 값은 a1 + a2 + a3 이고
8번째 값은 a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8
이므로 서로 빼준다면
a4~a8까지의 합만 남는다.

위와 같은 개념을 사용하여 N이 크든 작든 각 인자마다 1번의 계산만 하면 원하는 값을 구할 수 있다.

누적합으로 코드를 다시 작성해보면

const PrefixAnswer = (N, list) => {
  let prefix = [];
  const result = [];
  // for문 외부 변수로 선언
  let sum = 0;

  for (let i = 0; i < list.length; i++) {
    sum += list[i];
    // 각 리스트 순회하며 누적합 배열 생성
    prefix.push(sum);
  }

  prefix.forEach((sum, index) => {
    if (index >= N - 1) {
 	// 누적합 배열 순회하며 원하는 값 연산
      result.push(sum - (prefix[index - N] || 0));
    }
  });
  
  console.log(prefix);  // [ 3,  1, -3, -12, -12, -9, -2, 11,  19,  16]

  console.log(result); // [ -12, -12, -3, 14, 31, 28 ]
  
  // 최댓값 도출
  console.log(Math.max(...result))
};