[과제] Dynamic programming

1. N을 1, 2, 3의 합으로 나타내기

예를 들어 $N=5$면 다음과 같이 나타낸다.

$4$

$= 1 + 1 + 1 + 1$

$= 1 + 1 + 2$

$= 1 + 2 + 1$

$= 2 + 1 + 1$

$= 2 + 2$

$= 1 + 3$

$= 3 + 1$

 

public static int solve(int n) {
    int[] a = new int[n];
        
    a[0] = 0;
    a[1] = 1; 
    a[2] = 1; 
    a[3] = 2; 
        
    //from idx=4 to idx=n
    for(int i = 4; i < n; i++) {
        a[i] = a[i - 2] + a[i - 3] + a[i - 4];
    }
    
    return a[n - 1];
}

인덱스가 헷갈리면 아래 코드를 보자.

public static int solve(int n) {
    int[] a = new int[n + 1];
    
    a[1] = 1;
    a[2] = 2;
    a[3] = 4; 
        
    for(int i = 4; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2] + a[i - 3];
    }
    
    return a[n];
}

주어진 $N$을 $1 +(N-1),\; 2 + (N-2),\; 3 +(N-3)$으로 보면 $N-1$을 만드는 경우의 수, $N-2$를 만드는 경우의 수, $N-3$를 만드는 경우의 수의 합이 된다.

나는 $a[i]$를 '$i$를 $1,\;2,\;3$의 합으로 나타내는 경우의 수'로 정의했으므로 위와 같은 풀이가 성립한다.

만약에 $1,\; 2,\; 3$이 아닌 $3,\; 4,\; 5$의 합으로 나타내는 것이 문제였다면 $a[i]=a[i-3]+a[i-4]+a[i-5]$가 됐을 것.

 

Time complexity: $O(n)$

 

 

2. 치즈

테이블의 각 요소를 그 위치까지 오면서 먹을 수 있는 치즈의 최대 개수로 정의하면,
즉 $a[i][j]$의 값을 $(1,\; 1)$부터 $(i,\; j)$까지 이동하면서 먹을 수 있는 치즈의 최대 개수라 하면 다음과 같이 풀 수 있다.

public static int solve(int n, int[][] a) {
    //a[i][j] = (i, j)까지 오면서 먹을 수 있는 치즈의 최대 개수
    
    //Initialization
    for(int i = 1; i < n; i++) {
        a[i][0] += a[i - 1][0]; //1st column
        a[0][i] += a[0][i - 1]; //1st row
    }
 
 
    /*
     * 현재 위치로 오는 경로는 왼쪽으로부터 오거나 밑에서 올라오거나
     * 따라서 그 둘 중 큰 쪽을 선택한다. 
     */
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < n; j++) {
            a[i][j] += Math.max(a[i - 1][j], a[i][j - 1]);
        }
    }
    
    return a[n - 1][n - 1];
}

각 위치로 도달하는 방법은 왼쪽에서 오거나 밑에서 오는 것 뿐이다.

따라서 $A[i][j]$는 $A[i-1][j]$와 $A[i][j-1]$ 중 더 큰 값이다.

 

Base case는 테이블의 왼쪽과 아래 가장자리로, 이 부분은 아래에서 올라오거나 왼쪽에서 오는 경우 중 하나만 적용된다.

즉 왼쪽의 가장자리는 아래에서부터 더해 $a[i][0] += a[i-1][0]$로 초기화하고,

아래의 가장자리는 $a[0][i] += a[0][i-1]$로 초기화한다.

 

Time complexity: $O(n^2)$

 

 

 

 

 

 

3. 동전

이 문제는 greedy algorithm으로도 풀 수 있(다고 들은 것 같)다.

public static void main(String[] args) {
    int k = 365;    
    int[] coins = new int[] {1, 4, 7, 13, 28, 52, 91, 365};
    int[] a = new int[k + 1];
 
    System.out.println(solve(a, coins, k));
}
    
/*
 * 최소 금액이 1원보다 큰 경우 나타낼 수 없는 K가 발생한다
 * 나타낼 수 없는 금액은 어떻게 처리하지...
 */
public static int solve(int[] a, int[] coins, int k) {
    a[0] = 0; //sentinel
    for(int i = 1; i < coins[0]; a[i++] = 0);
    for(int i = coins[0]; i <= k; i++) {
        a[i] = a[i - coins[0]] + 1;
        for(int j = 1; j < coins.length && coins[j] <= i; j++) {
            a[i] = Math.min(a[i], a[i - coins[j]] + 1);
        }
    }
 
    return a[k];
}

$a[i]$ = Nadiria의 동전으로 $i$원을 나타낼 때 필요한 동전의 최소 개수.

15행:
Base case.
최소 금액 미만의 금액은 나타낼 수 없으므로 0.

16행:
$i$원을 나타내는 데에 필요한 동전의 수는 $i$에서 어떤 동전 $coin[j]$의 금액을 뺀 금액을 나타내는 데에 필요한 경우의 수에 $coin[j]$의 수 1을 더한 것으로 나타낼 수 있다.
즉 $i$원을 나타내는 데에 필요한 동전의 수는
$\min\{$
    (1원짜리 동전 1개 + (k-1)원을 나타내는 동전의 수),
    (4원짜리 동전 1개 + (k-4)원을 나타내는 동전의 수),
    (7원짜리 동전 1개 + (k-7)원을 나타내는 동전의 수),
    (13원짜리 동전 1개 + (k-13)원을 나타내는 동전의 수),
    (28원짜리 동전 1개 + (k-28)원을 나타내는 동전의 수),
    (52원짜리 동전 1개 + (k-52)원을 나타내는 동전의 수),
    (91원짜리 동전 1개 + (k-91)원을 나타내는 동전의 수),
    (365원짜리 동전 1개 + (k-365)원을 나타내는 동전의 수),
$\}$

다.

 

Time complexity: $O(K)$

주어진 금액 $K$에 선형적으로 비례함

 

 

 

4. 최대합 부분배열

public static void main(String[] args) {
    int[] a = new int[] {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
    System.out.println(solve(a));
}
 
public static int solve(int[] a) {
    //m[i] = sum(a[0..i])
    int[] m = new int[a.length];
    
   m[0] = a[0];
    for(int i = 1; i < m.length; i++) {
       m[i] = Math.max(a[i] + m[i - 1], a[i]);
    }
        
    return max(m, 0);
}

7행의 주석에 써놨듯이 $m[i]$는 $a[0..i]$에서 합이 최대인 부분배열의 합이다.
따라서 주어진 $n$에 대해 $m$의 길이는 $n$이다.

 

$a$를 한 요소 씩 훑으면 다음의 두 선택지가 있다.

1) 현재까지 만들어진 부분배열의 끝에 $a[i]$를 추가한다.

2) 현재까지 만들어진 부분배열은 모두 버리고 $a[i]$부터 다시 부분배열을 만든다.

 

첫 번째 경우 $m[i]$는 $m[i-1] + a[i]$가 된다.

즉 $i$에서 현재까지 만들어진 부분배열의 합은 $m[i-1]$이므로 여기에 $a[i]$를 더하면 된다.

 

두 번째 경우 $m[i]$는 $a[i]$가 된다. 현재까지 만들어진 부분배열 $m[i-1]$은 버리고 $a[i]$부터 다시 부분배열을 만드는 것이다.

 

합을 최대로 하는 것이 목적이므로 두 경우 중 값이 더 큰 경우를 선택한다.

 

이 과정을 $i=n$까지 반복하고 나면 $m[i]$에는 $A[0..i]$에서 최대합 부분배열의 합이 저장되어 있다.

문제에서 원하는 것은 가장 큰 합이므로 $m[0..i]$의 최대값이 정답이 된다.

 

 

Time complexity: $O(n)$

배열 $m$을 채움 -> $O(n)$

$m$에서 최대값을 찾음 -> $O(n)$회

따라서 시간 복잡도는 $O(n)$이 된다.

 

 

 

5. 최대곱 부분배열

 

딱 보고 최대합 부분배열이랑 똑같이 하면 되겠다 싶었다.

public static void main(String[] args) {
    int[] a = new int[] {0, 14, 0, -7, 0, 5, 0, -6, 12, -7, 0};
    System.out.println(solve(a));
}
 
public static int solve(int[] a) {
    int[] max = new int[a.length];
    int[] min = new int[a.length];
    
    max[0] = min[0] = a[0];
    for(int i = 1; i < a.length; i++) {
        int[] temp = new int[] { a[i]*max[i - 1], a[i], a[i]*min[i - 1] };
        max[i] = max(temp, 0);
        min[i] = min(temp, 0);
    }
    
    return max(max, 0);
}

어림도 없지

 

핵심은 두 개의 배열이다.

0 이상의 수만 있다면 최대합 부분배열이랑 똑같이 해도 상관 없지만 문제에서는 음수도 포함하고 있다.

이 음수가 문제다. 음수끼리 곱하면 더 큰 양수가 될 수 있기 때문에 이 경우를 따로 생각해줘야 한다. 
때문에 두 개의 배열이 필요하다. 한 배열에는 최대값을, 한 배열에는 최소값을 저장한다.

최소값에 음수를 곱하면 최대값이 될 수 있기 때문이다.

 

따라서 다음의 세 선택지가 있다.

1) 현재까지 만들어진 최대값(양수)에 $a[i]$를 곱한다.

2) 현재까지 만들어진 부분배열을 버리고 $a[i]$부터 다시 부분배열을 만든다.

3) 현재까지 만들어진 최소값(음수)에 $a[i]$를 곱한다.

 

$max$에는 이 세 선택지 중 값이 가장 큰 경우, $min$에는 가장 값이 작은 경우가 저장된다.

따라서 $max$에 의해 양수와 양수의 곱이 최대인 경우를, $min$에 의해 음수와 음수의 곱이 최대인 경우를 모두 생각할 수 있다.

 

Time complexity: $O(n)$