[073] 알고리즘: Dynamic Programming(DP)

 

2024.08.23(금)
 
알고리즘8일차

특강이기에
세부 내용은 노션에 기록
티스토리에는 출퇴근 복습용 코드만 기록

 

DP는 확실히 코드가 짧다.

★대신 dp가 의미하는 값이 무엇인지 파악하는 것이 매우 중요★

 

코치님 답변을 상세하게 기록했으니,

Top-down과 Bottom-up을 비교하면서 코드 이해해보자!

 

---

 

Dynamic Programming (DP)

• 큰 문제를 작은 문제들로 나누어 해결한 후, 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법
  • 중복 하위 문제(overlapping subproblem)
  • 속도 향상(memorization, dp table)
• 완전 탐색의 경우에도 재귀로 푸는 경우가 많았음

 

Top-down과 Bottom-up

• 시간복잡도는 동일하고, 선호하는 방식에 대한 차이임
• Top-down: memorization / Bottom-up: dp table

 

---

 

피보나치 수열

• 완전탐색(재귀)로 풀 경우 시간복잡도: 2의 n승
  • overlapping subproblem
• DP의 시간복잡도: o(n)
  • 메모리를 쓰되, 시간을 줄이는 기법
  • 완전탐색을 문제를 풀면서, DP로 풀 수 있 수 있지 않을까? 생각하기

Map<Integer, Integer> memo = new HashMap<>();
int fibo(int n) {
    if(n == 1 || n == 2){
    	reutrn 1;
    }
  
  	if(!memo.containKey(n)){
    memo.get(n, fibo(n-1) + fibo(n-2);
	}

	return memo.get(n);
    }

 

• Bottom-up 방식을 사용해서 구현
  • for문 & 시간복잡도는 동일함!
  • (선호하는 방식의 차이임)

피고나치수열 DP Bottom-up 방식

 

---

이건 외우자!

 

문제: 동전 교환

• 여러 종류의 동전을 나타내는 정수 배열 coins가 주어집니다.
  또한, amount라는 총 금액이 주어집니다.각 동전의 개수는 무한히 많다고 가정할 수 있습니다.
• 이 금액을 만들기 위해 필요한 최소 동전의 수를 반환하세요.
  만약 이 금액을 주어진 동전으로 만들 수 없다면 -1을 반환하세요.

 

프로그래머스 동전 교환

 

 

정답 코드:

• Top-down

import java.util.*;

class Solution {
    final int LIMIT = 10001;

    public int coinChange(int[] coins, int amount) {
				//✅ memo를 만든다.
        int[] memo = new int[amount+1];
        Arrays.fill(memo, LIMIT);
        return dp(memo, coins, amount);
    }

    int dp(int[] memo, int[] coins, int amount) {
				//✅ 현재 액수(amount)가 0이면, 0을 반환한다.
        if (amount == 0) return 0;

        int result = LIMIT;
				//✅ coins의 각 동전을 살펴본다.
        for (int coin : coins) {
						//✅ 현재 동전을 사용하고 남은 금액이 0 이상일 때,
            if (amount - coin >= 0) {
								//✅ 남은 금액에 대한 조합 가능한 동전 최소 개수를 memo에 저장하지 않았다면,
                if (memo[amount - coin] == LIMIT) {
										//✅ 남은 금액에 대해 재귀 함수를 호출하고, 반환값을 memo에 저장한다.
                    memo[amount - coin] = dp(memo, coins, amount - coin);
                }
								//✅ 남은 금액에 대한 동전 조합이 가능하다면,
                if (memo[amount - coin] != -1) {
										//✅ 남은 금액에 대해 조합 가능한 동전 최소 개수를 계산한다.
                    result = Math.min(result, memo[amount - coin]);
                }
            }
        }
        //✅ 조합 가능한 동전 최소 개수가 존재하면, 1을 더하여 반환한다.
				//✅ 가능한 동전 조합을 찾지 못했다면, -1을 반환한다.   
        return (result == LIMIT) ? -1 : result + 1;
    }
}

 

• Bottom-up

import java.util.*;

class Solution {
    final int LIMIT = 10001;

    public int coinChange(int[] coins, int amount) {
				//✅ amount+1 크기의 dp를 만들고, 10001로 초기화한다.
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, LIMIT);
				//✅ dp의 0번째 값을 0으로 초기화한다.
        dp[0] = 0;
				//✅ 0부터 amount까지 순회한다.
        for (int i = 0; i < amount; i++) {
            if (dp[i] == LIMIT) continue;
						//✅ coins의 각 동전을 살펴본다.
            for (int coin : coins) {
                if (i + coin > amount || i + coin < 0) continue;
								//✅ 현재 값과 선택한 동전의 합이 목표 금액(amount) 이하일 경우,
                if (dp[i + coin] > dp[i] + 1) {
										//✅ 점화식에 따라 다음 금액(현재 값과 선택한 동전의 합)에 대한 조합 가능 최소 동전 개수를 저장한다.
                    dp[i + coin] = dp[i] + 1;
                }
            }
        }
				//✅ 목표 금액에 대해 조합 가능 최소 동전 개수가 10001이면, -1을 반환한다.
				//✅ 아니라면, 계산한 목표 금액에 대해 조합 가능 최소 동전 개수를 반환한다.
        return (dp[amount] == LIMIT) ? -1 : dp[amount];
    }
}