LeetCode Perfect Squares (JavaScript), BFS, DP

링크 : https://leetcode.com/problems/perfect-squares/description/

문제 설명

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

• 1 <= n <= 104

---

문제 풀이

1. BFS 풀이

접근 방식

[현재 값, 카운트]를 기준으로 제곱 값을 더해가면서 n과 같은 경우를 찾는 것

단, 같은 숫자가 중복해서 발생할 수 있으므로 visited를 설정해 이미 검사한 숫자는 다시 검사하지 않도록 해야 함.

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    const queue = [[0, 0]];
    const visited = new Set(); // 방문한 숫자는 검사하지 않도록
    visited.add(0);

    while (queue.length > 0) {
        const [sum, count] = queue.shift();

        for (let i = 1; ; i++) {
            const nextSum = sum + i * i;
            if (nextSum === n) return count + 1;
            if (nextSum > n) break;

            if (!visited.has(nextSum)) {
                visited.add(nextSum);
                queue.push([nextSum, count + 1]);
            }
        }
    }
};

---

2. DP 풀이

접근 방식

i 번째 : 숫자 i를 만들기 위한 최소 횟수를 저장

점화식은 다음과 같이 정의할 수 있다.

dp[i - j * j] + 1 (j * j <= i)

i에서 어떤 제곱수(j * j)를 뺏을 때 최솟 값 중에서 1을 더한 값을 의미한다.

e.g. i가 4이고, j 가 1인 경우를 해석하면 다음과 같다.

dp[4] = 4이고 dp[4 - 1*1] = dp[3] = 3이다.

즉 4번째에서 1번째를 뺀 3숫자를 만드는 경우의 수에서 1을 더한 값이 4를 만들 수 있는 경우의 수이다. (3 + 1)

이런 식으로 j * j가 i보다 작거나 같을 때까지 반복하며 최소 경우의 수를 구해서 i번째에 할당한다.

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    const dp = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) {
        dp[i] = i;
    }

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }

    return dp[n];
};

---

결론

BFS와 DP형태로 문제를 해결할 수 있다.

최소 경로의 수를 구하는 문제로 DP보다 BFS가 더 효율적으로 해결이 될 수 있다.

그 이유는 BFS같은 경우 최소 경로를 만나면 즉시 종료를 시키기 때문에 어떠한 경우에서는 DP보다 효율적으로 동작할 수 있다.