📙[Algo] 24.03.07 탑 다운 DP

Dynamic Programming(DP), 동적 계획법 

• DP 중요도 ⇒ 코테에 굉장히 많이 나온다.
• 탑다운 DP와 바텀업 DP는 답까지 가는 사고 과정이 완전 다르다.
  +) DP 테크닉(DP dlc) : 토글링, 역추적, 비트마스킹, 행렬
• Dynaminc → 이름은 신경쓰지 말고, 알고리즘의 목적 생각

탑다운 DP 

BOJ14501. 퇴사

문제 요약 : 매일 상담이 잡혀있고, 각 상담마다 걸리는 기간과 수익이 있다. 이때, 상담을 적절히 선택하여 받을 수 있는 최대 수익을 구하는 문제.

• 문제풀이
  • 1️⃣ 백트랙킹으로 짠다.

static void recur(int cur, int total) {

    if (cur > N) return;

    if (cur == N) {
        answer = Math.max(answer, total);
        return;
    }

    recur(cur + arr[cur][0], total + arr[cur][1]);
    recur(cur + 1, total);
}

 

BOJ15486. 퇴사2

문제 요약 : 퇴사 문제와 같지만, N제한이 더 큼(150만).

• 기존 백트랙킹으로 하면 시간초과로 한다.
  • N제한이 작다면 충분히 백트랙킹으로 되는 문제

💡 DP 3단계 풀이 과정
1️⃣ 백트랙킹으로 짠다.
2️⃣ 함수 형태로 바꾼다. (리턴하는 방식으로) → 여기를 잘 이해해야 함
3️⃣ 메모이제이션 추가

• 2️⃣ 함수 형태로 바꾼다.
  ⇒ 지금 날짜(cur)로부터 앞으로 벌 수 있는 최대 금액을 return 하려고 함

 

static int recur(int cur) {

    // 범위를 벗어나는 경우는 상담을 받을 수 없기 때문에 무조건 큰 손해가 생기도록 return
    if (cur > N) return -1000000000;

    if (cur == N) return 0;

    return Math.max(recur(cur + arr[cur][0]) + arr[cur][1], recur(cur + 1));
}

 

그러나 아직은 시간초과 뜸

• 3️⃣ 메모이제이션 추가 : 이미 계산한건 또 계산 x
  즉, 최초로 계산된 recur(7), recur(6), recur(5)… 등의 return값을 배열에 저장해둔다.
  ⇒ dp 배열 만들기 → -1을 N개 채우고 시작

static int recur(int cur) {

    if (cur > N) return -1000000000;

    if (cur == N) return 0;

    // -1이 아니다 => 이미 recur(cur)을 구한 값이므로 배열에 기록된 거 꺼내기
    if (dp[cur] != -1) return dp[cur];

    // 배열 dp에 기록하기
    dp[cur] = Math.max(recur(cur + arr[cur][0]) + arr[cur][1], recur(cur + 1));
    return dp[cur];
}

 

파이썬은 통과가 안 될 수도 있다 ⇒ 나중에 탑다운 방식을 바텀업 방식으로 바꾸는 연습함.

 

피보나치 수열

앞의 두 수의 합이 바로 뒤의 수가 되는 수 (첫 번째 항은 0, 두 번째 항은 1로 시작)

static int fibo(int x){

    if (x <= 1) return x;

    return fibo(x - 1) + fibo(x - 2);

}

 

중복되는 부분은 메모이제이션을 한다.

static long[] dp;    // 구하려는 수(N) + 1 크기로 만들고 -1로 채움

static long fibo(int x){

    if (x <= 1) return x;

    if (dp[x] != -1) return dp[x];

    dp[x] = fibo(x - 1) + fibo(x - 2);
    return dp[x];

}

 

시간 복잡도

• N칸을 채워야 한다. ⇒ 테이블의 크기
• 한 칸을 채우기 위해 M개의 함수(연산)를 호출한다. ⇒ 함수 호출의 개수

⇒ 테이블의 크기 * 함수 호출 개수

💡 정리
✅ DP
백트랙킹이 너무 오래 걸린다. 근데, 중복 케이스를 너무 많이 보고 있다. 각 케이스의 정답을 저장해두고, 중복 케이스를 다시 본다면 저장해둔 걸 사용하자!
✅ 메모이제이션
정답을 저장하는 것
✅ 탑다운 DP
재귀 함수에서 메모이제이션을 이용해 시간복잡도를 줄이는 방법 

 

BOJ1149. RGB거리

문제 요약 : N개의 집에 빨강(R), 파랑(B), 초록(G)을 칠하려고 하며, 집마다 각각의 색을 칠할 때 드는 비용이 존재한다. 단, 서로 인접한 집끼리 같은 색이 되지 않도록 해야 한다. 이때 비용의 최솟값 구하는 문제.

1️⃣ 백트랙킹으로 짠다.

static void recur(int cur, int total, int prv){

    if (cur == N) {
        // answer 초기값 : 1 << 30 (2의 30제곱)
        answer = Math.min(answer, total);
        return;
    }

    for (int i = 0; i < 3; i++) {
        // 이전에 선택한 색깔은 pass
        if (i == prv) continue;

        recur(cur + 1, total + arr[cur][i], i);
    }

}

2️⃣ 함수 형태로 바꾼다.

재귀를 돌 때마다 현재 집에서 선택할 수 있는 색깔 중 비용이 가장 작은 것을 반환하게 된다.

ret을 지역변수로 선언한 이유는 각 집마다 최소 비용을 반환해야 하기 때문이다.

(즉, ret은 각 집에서 선택한 비용을 담고 있는 변수.)

static int recur(int cur, int prv){

    if (cur == N) {
        // 마지막 줄 까지 오면 더이상 들 비용이 엇다.
        return 0;
    }

    int ret = 1 << 30;
    for (int i = 0; i < 3; i++) {

        // 이전에 선택한 색깔은 pass
        if (i == prv) continue;

        ret = Math.min(ret, recur(cur + 1, i) + arr[cur][i]);
    }

    return ret;

}

3️⃣ 메모이제이션 추가

cur와 prv값에 따라 결과 값이 달라지므로, dp를 2차원으로 선언해서 기록할 수 있다. ⇒ dp[cur][prv] (만약 N가지 정보가 필요했다면 N차원으로 만들어서 기록)

static int recur(int cur, int prv){

    if (cur == N) {
        // 마지막 줄 까지 오면 더이상 들 비용이 없다.
        return 0;
    }

    if (dp[cur][prv] != -1) return dp[cur][prv];

    int ret = 1 << 30;
    for (int i = 1; i <= 3; i++) {

        // 이전에 선택한 색깔은 pass
        if (i == prv) continue;

        ret = Math.min(ret, recur(cur + 1, i) + arr[cur][i]);
    }

    dp[cur][prv] = ret;
    return ret;

}

 

BOJ12865. 평범한 배낭

문제 요약 : N개의 물건이 존재하고, 각 물건은 무게 W, 가치 V를 갖고 있다. 최대 K만큼의 무게를 들 수 있을 때, 나올 수 있는 가치의 최댓값을 구하는 문제.

1️⃣ 백트랙킹으로 짠다.

static void recur(int cur, int weight, int price) {

    if (weight > M) return;

    if (cur == N) {
        answer = Math.max(answer, price);
        return;
    }

    recur(cur + 1, weight + arr[cur][0], price + arr[cur][1]);
    recur(cur + 1, weight, price);
}

2️⃣ 함수 형태로 바꾼다.

현재 물건을 선택했을 때와 선택하지 않았을 때 중 가치의 최댓값 반환

static int recur(int cur, int weight) {

    if (weight > M) return -1000000000;

    if (cur == N) return 0;

    int ret = recur(cur + 1, weight + arr[cur][0]) + arr[cur][1];
    ret = Math.max(ret, recur(cur + 1, weight));

    return ret;
}

3️⃣ 메모이제이션 추가

// int[][] dp = new int[N][100010];

static int recur(int cur, int weight) {

    // weight이 M을 넘어가는 건 답이 되면 안 되므로 
    if (weight > M) return -1000000000;

    if (cur == N) return 0;

    if (dp[cur][weight] != -1) return dp[cur][weight];

    int ret = recur(cur + 1, weight + arr[cur][0]) + arr[cur][1];
    ret = Math.max(ret, recur(cur + 1, weight));

    dp[cur][weight] = ret;
    return ret;
}

탑다운 DP 특징

• 진입장벽이 높다. (백트랙킹 잘해야 한다.)
• 쉬운 문제, 어려운 문제 구분이 사라진다.

 

BOJ20544. 공룡 게임

문제 요약 : 맵에는 N개의 지점이 있고, 각 지점은 높이가 1또는 2인 장애물이 존재한다. 시작 지점은 1이고, 공룡이 앞으로 갈수록 지점을 나타내는 수가 증가한다. 공룡은 (1) 최대 2개의 인접한 장애물을 뛰어넘을 수 있으며(3개 이상 X), 두 장애물의 높이의 합이 4 이상이면 뛰어넘을 수 없다. (2) 시작 지점은 장애물이 없다. (3) 높이 2인 장애물은 무조건 하나 이상 존재해야 한다. N이 주어졌을 때 가능한 맵의 종류를 구하는 문제.

1️⃣ 백트랙킹으로 짠다.

static void recur(int cur, int cnt1, int cnt2, int two) {
    // cnt1 : 연속한 장애물 개수
    // cnt2 : 연속한 높이 2짜리 장애물 개수
    // two : 높이 2짜리 설치 여부

    // 연속된 장애물 개수가 3개 이상이거나, 연속한 높이 2짜리 장애물 2개는 불가능
    if (cnt1 > 2 || cnt2 >= 2) return;

    if (cur == N) {
        if (two == 1) answer++;

        return;
    }

    // 장애물 설치 X => 연속이 끊기므로 cnt1은 0으로,,
    recur(cur + 1, 0,0, two);
    // 장애물 높이 1짜리 설치
    recur(cur + 1, cnt1 + 1, 0, two);
    // 장애물 높이 2짜리 설치
    recur(cur + 1, cnt1 + 1, cnt2 + 1, 1);

}

2️⃣ 함수 형태로 바꾼다.

현재 지점(cur)에서 장애물 설치X, 1짜리 장애물 설치, 2짜리 장애물 설치했을 때 나올 수 있는 경우의 수를 반환한다.

static int recur(int cur, int cnt1, int cnt2, int two) {

    if (cnt1 > 2 || cnt2 >= 2) return 0;

    if (cur == N) {
        if (two == 1) return 1;
        else return 0;
        // 또는 return two해도 됨 
    }

    return recur(cur + 1, 0, 0, two) + recur(cur + 1, cnt1 + 1, 0, two) + recur(cur + 1, cnt1 + 1, cnt2 + 1, 1);
}

3️⃣ 메모이제이션 추가

cur, cnt1, cnt2, two값에 따라 결과 값이 달라지므로 4차원 dp 배열을 만든다.

// int[][][][] dp = new int[N][3][2][2];

static int recur(int cur, int cnt1, int cnt2, int two) {

    if (cnt1 > 2 || cnt2 >= 2) return 0;

    if (cur == N) return two;

    if (dp[cur][cnt1][cnt2][two] != -1) return dp[cur][cnt1][cnt2][two];

    dp[cur][cnt1][cnt2][two] = (int)((recur(cur + 1, 0, 0, two)
            + recur(cur + 1, cnt1 + 1, 0, two)
            + recur(cur + 1, cnt1 + 1, cnt2 + 1, 1)) % 1000000007);
    return dp[cur][cnt1][cnt2][two];
}