[Algorithm] DP

tngus2sh·2024년 9월 29일

algorithm

Algorithm

목록 보기

16/18

동적계획법

하나의 문제는 단 한 번만 풀도록 하는 알고리즘
큰 문제를 작은 문제로 나누어서 해결하는 방법
큰 문제 해결 위해 작은 문제를 활용 → 점화식 만들 수 있음
분할과 정복이랑 다르게 이전 연산 기록하여 재사용

메모이제이션(Memoization)

작은 문제 연산 값 기록하고 필요한 순간에 다시 연산하지 않고 기록했던 값 사용
중복 계산 줄여줌

Bottom-up & Top-down

Top-down

큰 문제 해결하는데 작은 문제가 해결되지 않는다면 그 때 작은 문제 해결하는 방법
주로 재귀함수 통해서 구현
피보나치 수열 구하기

Bottom-up

작은 문제를 해결하면서 큰 문제를 해결하는 방법
주로 반복문으로 구현

유형

조합

${n}C{k} = {n-1}C{k} + {n-1}C{k-1}$

int[][] combination = new int[N+1][N+1];

combination[1][0] = 1;
combination[1][1] = 1;

// nCk = n-1Ck + n-1Ck-1
for (int i = 2; i < N+1; i++) {
    combination[i][0] = 1;
    for (int j = 1; j < i+1; j++) {
        combination[i][j] = combination[i-1][j] + combination[i - 1][j - 1];
    }
}

배낭문제

조합 최적화의 문제로, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있는 경우, ‘일정 가치’와 ‘무게’가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제입니다.

과정

i번째 물건이 배낭의 무게 한도보다 무거우면 넣을 수 없으므로 i-1개의 물건들을 가지고 구한 전 단계의 최적값을 그대로 가져옵니다.
그렇지 않은 경우, i번째 물건을 위해 i번째 물건만큼의 무게를 비웠을 때의 최적값에 i번째 물건의 가격을 더한 값 vs i - 1개의 물건들을 가지고 구한 전 단계의 최적값 중 큰 것을 선택합니다.

import java.io.*;
import java.util.*;
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());//물건 개수int k = Integer.parseInt(st.nextToken());//최대 무게int[][] dp = new int[n+1][k+1];
    int[] w = new int[n+1];//물건의 무게들 int[] v = new int[n+1];//물건의 가치들for (int i = 1; i <= n; i++) {
      st = new StringTokenizer(br.readLine());
      w[i] = Integer.parseInt(st.nextToken());
      v[i] = Integer.parseInt(st.nextToken());
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= k; j++) {
        if (w[i] <= j) {
          dp[i][j] = Math.max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]);
        } else {
          dp[i][j] = dp[i-1][j];
        }
      }
    }
    System.out.print(dp[n][k]);
  }
}