[TIL] 05.29

📙  공부 한 것

알고리즘

-1003  다리놓기 (동적계획법)

-1010 피보나치함수 (동적계획법)

-1436 영화감독 숌

- 동적계획법

 

🔍 시도해본 것

서로 다른 N개중 중복을 허용하지 않고 r개를 뽑는 경우의 수를 작성해야하는데,

이 방법을 코드로 메모이제이션을 이용해서 구현하는 방법을 몰랐다.

예를들면, 4개의 동쪽다리와 3개의 서쪽다리가 있을때,

(3,1,4) 와 (1,3,4)를 동일하게 한가지 경우의 수로 세아리는 것이다. (크로스x)

 

💡 알게된 점

 

조합 공식의 성질

조합공식 1

조합 성질 1

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

조합 성질 2

 

dp[i][j] =1 , dp[i][0] = 0

 

위 두 가지 조합성질을 이용해서, 메모이제이션을 이용해 동적계획법으로 구현할 수 도있다.

 

 

동적계획법이란? 

큰 문제를 작은 문제로 나누어 푸는 알고리즘 기법이다. 이를 통해, 중복되는 계산을 피하고 효율적으로 문제를 해결할 수 있다.

 

예시 : 피보나치 수열

fib(0) = 0

fib(1) = 1

fib(n) = fib(n-1) + fib(n-2) (N=2),

 

이를 재귀함수로 구현하면 다음과 같다.

 

public static int fib(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}
 

하지만 위 방법은 n이 커질 수록, 지수적으로 시간이 증가해서 비효율적인 코드이다.

동적 계획법을 사용해서 피보나치 수열을 구하는 방법은 다음과같다.

public static int fib(int n) {
    int[] memo = new int[n+1];
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i <= n; i++) {
        memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
}
 

 

위 코드에서는 memo에 이미 구한 값을 저장해서, 중복 계산을 피한다. 이를 통해, 피보나치 수열을 효율적으로 구할 수 있다.

호출 이미지