문제 설명
숫자 배열 arr을 첫 번째 인수로, 숫자 num(num은 arr의 길이 이하)을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 배열 arr을 최대 num개의 인접한(non-empty) 그룹으로 분할해야 하며, 이때 어떤 요소도 빠짐없이 모든 요소가 반드시 하나의 그룹에 속해야 합니다.
가능한 모든 분할 방법 중에서 각 그룹의 평균값을 모두 더한 합이 가장 커지는 분할을 찾고, 그 최댓값을 반환하면 됩니다.
예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
입력
const arr = [10, 2, 3, 4, 10]; const num = 3;
출력
const output = 23;
출력 설명
배열을 다음과 같이 세 개의 그룹으로 나누면,
[10], [2, 3, 4], [10]
각 그룹 평균의 합은 다음과 같이 계산됩니다.
10 + (9 / 3) + 10 = 23
이 값이 가능한 모든 분할 방법 중에서 가장 큰 값입니다.
동적 계획법(DP) 접근 방식
모든 분할 조합을 일일이 확인하는 완전 탐색은 경우의 수가 기하급수적으로 늘어나 비효율적입니다. 따라서 이 문제는 동적 계획법을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 위치에서 새로운 그룹을 시작하거나, 기존 그룹에 요소를 추가하는 두 가지 선택지를 고려합니다.
- 남은 그룹 개수와 현재 그룹의 크기를 상태로 사용하여, 각 상태에서 얻을 수 있는 평균 합의 최댓값을 행렬(matrix)에 저장합니다.
- 새 그룹을 시작할 때는 지금까지 완성된 그룹의 평균을 결과에 더하고, 그룹을 확장할 때는 평균 계산을 뒤로 미루어 최종적으로 최적의 분할을 찾아냅니다.
예제 코드
다음은 위 접근 방식을 구현한 전체 코드입니다.
const arr = [10, 2, 3, 4, 10];
const num = 3;
const greatestSum = (arr, num) => {
const sum = (arr = []) => arr.reduce((acc, num) => acc + num, 0)
let matrix = new Array(num + 1).fill(0).map(() => new Array(arr.length + 1).fill(0))
for (let index = arr.length; index >= 0; index--) {
const current = new Array(num + 1).fill(0).map(() => new Array(arr.length + 1).fill(0))
for (let currentK = num; currentK >= 0; currentK--) {
for (let count = arr.length - 1; count >= 0; count--) {
if (index === arr.length && currentK === num) {
current[currentK][count] = 0
} else if (index < arr.length && currentK < num) {
current[currentK][count] = Math.max(
matrix[currentK][count + 1],
matrix[currentK + 1][0] + sum(arr.slice(index - count, index + 1)) / (count + 1)
)
} else {
current[currentK][count] = -Infinity
}
}
}
matrix = current
}
return matrix[0][0]
}
console.log(greatestSum(arr, num));출력 결과
23
코드를 실행하면 배열 [10, 2, 3, 4, 10]을 [10], [2, 3, 4], [10]으로 나누었을 때의 평균 합인 23이 정상적으로 출력됩니다.