[JS] 동적 계획법 (DP)문제 / 중복계산방지, O(n)

🚀 문제

n개의 계단을 오를 때, 한 번에 1계단 또는 2계단을 오를 수 있다. 계단을 오르는 방법의 수를 반환하는 함수를 작성하시오.

      
      
      
    
function climbStairs(n) {
  // 여기에 코드 작성
}

console.log(climbStairs(5)); // 8

---

🔹 코드

      
      
      
    
function climbStairs(n) {
   	if(n < 3) return n;
    return climbStairs(n-1) + climbStairs(n-2);
}

console.log(climbStairs(6)); // 8

 

---

📌 동적 계획법 (DP)

🔎 1️⃣ 문제가 묻는 것

동적 계획법(DP)은 복잡한 문제를 여러 개의 작은 문제로 나누어 푸는 알고리즘 설계 기법입니다. 보통 최적화 문제나 계산을 효율적으로 해결해야 할 문제에서 유용하게 사용됩니다. 주로 두 가지 방식인 탑다운(Top-Down) 방식과 바텀업(Bottom-Up) 방식으로 구현할 수 있습니다.

✅ 핵심 개념:

1. 문제 분할:
   • 문제를 더 작은 하위 문제로 나누어 풀고, 그 결과를 저장하여 중복 계산을 방지합니다.
   • 예를 들어, 피보나치 수열 문제에서는 fibonacci(n)을 fibonacci(n-1)과 fibonacci(n-2)로 나누어 해결합니다.
2. 메모이제이션 (Top-Down 방식):
   • 하향식 접근법: 큰 문제를 풀기 위해 하위 문제를 재귀적으로 풀고, 그 결과를 메모리에 저장하여 중복 계산을 피합니다.
   • 메모리 사용량은 하위 문제의 개수에 비례합니다.
3. 타뷸레이션 (Bottom-Up 방식):
   • 상향식 접근법: 가장 작은 문제부터 차례대로 풀어가며 결과를 저장합니다.
   • 보통 배열이나 테이블을 사용하여 모든 하위 문제를 풀고 최종 문제의 해결책을 찾습니다.
4. 시간 복잡도 & 공간 복잡도:
   • 동적 계획법을 사용하면 보통 O(n) 의 시간 복잡도로 최적화할 수 있습니다.
   • 공간 복잡도는 메모이제이션을 사용하는 경우 O(n) 이나, 상향식 방식에서는 O(1) 로 최적화할 수 있는 경우도 있습니다.
5. 중복 계산 방지:
   • DP의 핵심은 중복된 계산을 방지하는 것입니다. 동일한 하위 문제를 여러 번 계산하지 않도록 메모리에 값을 저장해 두고 재사용합니다.

1.  

---

 

 

2️⃣ 일반적인 풀이 방법

1. 메모이제이션 (Top-Down 방식)

• 문제를 해결하기 위해 재귀적으로 호출하고, 이미 계산된 값을 메모리에 저장하여 중복 계산을 방지합니다.

      
      
      
    
function fibonacci(n, memo = {}) {
    if (n <= 1) return n;  // 기본 값 처리
    if (memo[n]) return memo[n];  // 이미 계산된 값이 있으면 그 값을 반환
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);  // 값 저장
    return memo[n];
}

• 시간 복잡도: O(n)
• 공간 복잡도: O(n) (메모이제이션 객체)

2. 타뷸레이션 (Bottom-Up 방식)

• 하위 문제부터 차례대로 풀어나가면서 테이블에 결과를 저장하여 최종 문제의 해결책을 구합니다.

      
      
      
    
function fibonacci(n) {
    if (n <= 1) return n;  // 기본 값 처리
    let dp = [0, 1];  // 초기 값 설정
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // DP 테이블에 결과 저장
    }
    return dp[n];
}

• 시간 복잡도: O(n)
• 공간 복잡도: O(n) (DP 테이블)

3. 공간 최적화 (타뷸레이션)

• 상향식 방식에서, 필요한 최소한의 공간만을 사용하여 O(1) 의 공간 복잡도로 최적화할 수 있습니다.

      
      
      
    
function fibonacci(n) {
    if (n <= 1) return n;
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        let temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

 

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

---

 

 

3️⃣ 동적 계획법 적용 문제 예시

문제 1: 피보나치 수열

피보나치 수열은 전형적인 DP 문제로, 중복 계산을 피하고 최적화된 방식으로 해결할 수 있습니다.

문제 2: 계단 오르기 문제

n개의 계단을 오를 때, 한 번에 1칸 또는 2칸을 오를 수 있을 때, 몇 가지 방법으로 계단을 올라갈 수 있는지 구하는 문제입니다.

      
      
      
    
function climbStairs(n) {
    if (n <= 2) return n;
    let dp = [0, 1, 2];  // 초기값 설정
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // 이전 두 계단의 값을 합침
    }
    return dp[n];
}

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

문제 3: 0/1 배낭 문제

최대 용량 W인 배낭에 물건을 담을 때, 물건의 가치와 무게가 주어졌을 때 가방에 담을 수 있는 최대 가치를 구하는 문제입니다.

      
      
      
    
function knapsack(weights, values, W) {
    let n = weights.length;
    let dp = Array(W + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        for (let w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

• 시간 복잡도: O(n * W)
• 공간 복잡도: O(W)

---

4️⃣ 요약

• 동적 계획법(DP) 은 최적화 문제를 해결하는 데 중요한 기법입니다. 재귀적 문제를 풀 때 중복 계산을 방지하고, 시간 복잡도를 최적화합니다.
• DP는 탑다운(메모이제이션) 방식과 바텀업(타뷸레이션) 방식으로 구현할 수 있으며, O(n) 시간 복잡도를 달성할 수 있습니다.
• DP의 공간 복잡도는 메모이제이션 방식에서 O(n) 이지만, 바텀업 방식에서는 공간 최적화를 통해 **O(1)**로 줄일 수 있습니다.