JavaScript로 양의 정수 분할(파티션)의 가능한 모든 방법 구하기

양의 정수 n의 분할(partition)이란 n을 하나 이상의 양의 정수 합으로 표현하는 방법을 의미합니다. 이때 덧셈 순서만 다른 두 식은 같은 분할로 간주합니다.

예를 들어, 4는 다음과 같이 다섯 가지 방법으로 분할할 수 있습니다.

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

문제 정의

양의 정수 하나를 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 해당 정수를 분할할 수 있는 모든 경우의 수를 계산하여 반환해야 합니다.

접근 방식: 동적 프로그래밍(Dynamic Programming)

이 문제는 동적 프로그래밍으로 효율적으로 해결할 수 있습니다. 2차원 배열 arr[i][j]는 다음을 의미합니다.

• i: 사용할 수 있는 최대 부분 값
• j: 만들고자 하는 목표 합

즉, arr[i][j]는 1부터 i까지의 정수만 사용하여 j를 만드는 분할의 개수입니다. 각 단계에서 특정 값 i를 포함하지 않는 경우(exclusive)와 포함하는 경우(inclusive)를 더해 점화식을 세웁니다.

• 초기 조건: 목표 합이 0일 때는 빈 분할 하나가 존재하므로 arr[i][0] = 1, 사용 가능한 값이 없으면 arr[0][j] = 0으로 설정합니다.
• i > j인 경우, i보다 큰 값은 사용할 수 없으므로 arr[i][j] = arr[i-1][j]입니다.
• 그 외의 경우에는 arr[i][j] = arr[i-1][j] + arr[i][j-i]로 계산합니다.

예제 코드

다음은 전체 구현 코드입니다.

const findPartitions = (num = 1) => {
    const arr = Array(num + 1).fill(null).map(() => {
        return Array(num + 1).fill(null);
    });
    // 목표 합이 0인 경우: 빈 분할 1개
    for (let i = 0; i <= num; i += 1) {
        arr[i][0] = 1;
    }
    // 사용 가능한 값이 없는 경우
    for (let j = 1; j <= num; j += 1) {
        arr[0][j] = 0;
    }
    for (let i = 1; i <= num; i += 1) {
        for (let j = 1; j <= num; j += 1) {
            if (i > j) {
                arr[i][j] = arr[i - 1][j];
            } else {
                const exclusive = arr[i - 1][j]; // i를 사용하지 않는 경우
                const inclusive = arr[i][j - i]; // i를 사용하는 경우
                arr[i][j] = exclusive + inclusive;
            }
        }
    }
    return arr[num][num];
};
console.log(findPartitions(4));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

5

앞서 확인한 것처럼 4는 총 5가지 방법으로 분할할 수 있으므로 결과가 올바르게 출력됩니다. 이 알고리즘의 시간 복잡도는 O(n²)이며, 재귀적 완전 탐색보다 훨씬 효율적으로 큰 수도 처리할 수 있습니다.