과제 : 최대합 부분 배열

모던 JavaScript 튜토리얼 내용 중 일부 문제를 정리한 내용입니다.

숫자로만 구성된 배열이 있을 때 인접한 요소의 총합이 최대인 arr의 부분 배열을 찾고 그 부분 배열의 요소들의 합을 리턴하는 문제다. 요소 전체가 음수라면 아무 요소도 선택하지 않아서 부분 배열이 빈 배열이 되어 합이 0이 되어야 한다. 이런 문제를 예전에 봤던 것 같은데 다시 보니 또 새롭다.. 아무튼 문제 풀이를 따라가며 아래 기록을 남긴다.

let arr = [-1, 2, 3, -9, 11];

만들 수 있는 모든 배열의 합을 계산하려면 중첩 반복문을 사용한다면 아래처럼 모든 경우의 수의 합을 구해서 비교할 수 있다.

// -1부터 시작
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// 2부터 시작
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// 3부터 시작
3
3 + (-9)
3 + (-9) + 11

// -9부터 시작
-9
-9 + 11

// 11부터 시작
11

중첩 반복문의 안쪽 반복문이 각 요소를 순회하며 sumFixedStart 값을 구하고 그 값을 maxSum 과 계속 비교해 최대값을 구한다. 이런 중첩반복문은 다시 봐도 헷갈리는 느낌이다. 하나씩 대입을 해보면서 확인해야 한다.

function getMaxSubSum(arr) {
  let maxSum = 0; // 기본 값

  for (let i = 0; i < arr.length; i++) {
    let sumFixedStart = 0; 
    for (let j = i; j < arr.length; j++) { // 초기값을 i 로 세팅하고 순회
      sumFixedStart += arr[j]; // j 인덱스의 값을 더하고
      maxSum = Math.max(maxSum, sumFixedStart); // 최대값과 비교해서, 최대값 새롭게 갱신하고 다시 비교
    }
  }
  return maxSum; // 최종 최대값 반환
}

이 과제에서는 위와 같은 방식은 성능 이슈가 있다고 한다. 시간 복잡도에 대한 개념이 나오는데 이부분은 추가 공부가 필요하고,(n^2 가 된다고) 일단 이럴 경우 배열 크기를 2배로 늘리면 알고리즘은 4배 더 오래 걸린다고 한다. 그래서 아래처럼 fot .. of 반복문을 사용해 배열을 순회하며 현재의 부분합을 저장해 비교하는 방식을 추천한다. 중첩해서 반복문을 쓸 필요가 없는 것이다.

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) { // 배열의 각 요소를
    partialSum += item; // partialSum에 더합니다.
    maxSum = Math.max(maxSum, partialSum); // 최대값을 기억해 놓습니다.
    if (partialSum < 0) partialSum = 0; // 음수가 되면 0을 대입합니다.
  }

  return maxSum;
}

이렇게 한번만 반복한다면 for.. of 의 사용 여부가 문제가 아니었던 것 같긴한데. 아무튼 빠른 풀이는 이렇다. 다음에 이런 문제를 풀어야 한다면 다시 한번 살펴봐야 겠다.