[Algorithm] Backtracking 로직을 Top-down DP 로직으로 변경해 보자 (Feat. 백준 14863번)

YUSHIN KIM·2024년 7월 26일
DPboj

Algorithm

목록 보기
1/20

Dynamic Programming

오늘은 다이나믹 프로그래밍을 사용한 문제해결 방법론 중 Top-down 방식, 그 중에서도 완전탐색이 필요한 상황에서 짜여진 Backtracking 로직을 Top-down DP 로직으로 개선하는 방법에 대해 정리해 보고자 한다.

다이나믹 프로그래밍이란 어떤 큰 문제의 해가 작은 문제의 해로부터 유도되고, 작은 문제가 불필요하게 반복되는 상황에서 작은 문제의 해를 테이블(메모리)에 저장함으로써 시간 복잡도를 획기적으로 개선하는 문제해결 방법론이다.

Bottom-up vs. Top-down

나는 원래 다이나믹 프로그래밍과 관련된 문제를 모두 Bottom-up 방식으로 해결하는 것을 선호했다. 문제는 배낭 문제, 타일 문제처럼 Bottom-up 방식으로 해결하는 것이 편하거나, 애초에 그 방식이 잘 알려진 문제들도 있는 반면 그렇지 않은 문제도 많다는 것이었다.

잘 알려진 문제인 피보나치 수열 문제를 Bottom-up 로직, Top-down 로직으로 각각 구현해 보면 아래와 같다.

// Bottom-up Fibonacci Pseudo code
vector<unsigned long long> table(N, -1);
table[0] = 0;
table[1] = 1;

for (int i = 2; i < N; i++)
	table[i] = table[i-1] + table[i-2];
// Top-down Fibonacci Pseudo code
vector<unsigned long long> table(N, -1);
table[0] = 0;
table[1] = 1;

unsigned long long Fibonacci(int N) {
	if (table[N] != -1)
    	return table[N];
    
    table[N] = Fibonacci(N-1) + Fibonacci(N-2);
    return table[N];
}

이처럼 Bottom-up 로직은 for loop를 기반으로 이루어지고, Top-down 로직은 재귀 함수를 기반으로 이루어진다.

Top-down 로직이 필요한 상황

개개인의 문제풀이 스타일에 따라 Bottom-up 방식이 편한 사람도 있을 것이고, Top-down 방식이 편한 사람도 있을 것이다. 그러나 내가 경험한 바로는 잘 알지 못하는 문제는 Top-down 방식으로 시도하는 것이 편하다. 그 이유는 DP 문제 자체가 완전탐색을 전제로 하고 있기 때문에 일단 완전탐색 로직을 구현한 후 DP 로직으로 전환하면 실수도 덜하고 점화식을 떠올리기도 쉽기 때문이다.

예시: 백준 14863번

BOJ 14863

1. 완전탐색

먼저 백트래킹 로직을 구현해야 한다. 문제 조건을 보면 당연히 입력이 클 때 백트래킹 로직은 통과 불가능하지만, 작은 입력에 대해선 충분히 답을 낼 수 있다. 우리는 예제로 주어지는 작은 입력들로 백트래킹 로직을 검증하면 된다.

흔히 백트래킹 로직을 구현할 때 상태 값, 이 문제로 예를 들면 최대 모금액이나 현재까지 보낸 시간과 같은 값을 전역 변수로 관리하는 코드도 있는데 주의할 점은 상태 값을 외부의 변수에 담지 말고 재귀 함수의 매개변수나 반환 값에 담아야 한다는 것이다. 코드를 보면 이해가 될 것이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define INF 100000000

class Interval {
    public:
        int walkCost;
        int walkMoney;
        int bicycleCost;
        int bicycleMoney;
};

int N, K;
vector<Interval> interval;

ll DFS(int i, int remainingTime);

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K;
    interval.resize(N);
    for (int i = 0; i < N; i++)
        cin >> interval[i].walkCost >> interval[i].walkMoney >> interval[i].bicycleCost >> interval[i].bicycleMoney;
    
    cout << DFS(0, K);

    return 0;
}

ll DFS(int i, int remainingTime) {
    if (remainingTime < 0)
        return -INF;

    if (i == N)
        return 0;

    ll ret = max(
        DFS(i + 1, remainingTime - interval[i].walkCost) + interval[i].walkMoney,
        DFS(i + 1, remainingTime - interval[i].bicycleCost) + interval[i].bicycleMoney
    );
    
    return ret;
}

Backtracking result

코드를 제출하면 예상했던 대로 N > 20으로 제약 조건이 없는 상황에서 시간 초과가 걸리게 된다. N <= 20인 경우엔 잘 작동한다는 걸 확인했으므로 이제 DP 로직으로 개선해 볼 차례이다.

2. 점화식 및 테이블 구성

점화식과 테이블을 구성하는 과정은 매우 간단하다. 이것 때문에 Top-down DP 로직을 사용하는 것이다. 재귀 함수의 매개변수를 인덱스로 테이블을 구성하고, 반환 값을 테이블에 저장하도록 하면 된다.

앞서 나는 재귀 함수의 매개변수를 현재 탐색하고 있는 구간(i), 현재까지 남은 시간(remainingTime)으로 구성하였고, 최대 모금액(ret)을 반환하도록 하였다.

...
vector<vector<ll>> table;       // [curr interval][remaining time]
...
table.resize(N, vector<ll>(K + 1, -INF));
...

그러므로 테이블을 이렇게 구성해 주면 된다.

3. Top-down DP 로직으로 변경

기존의 종료 조건에 하나를 더 둔다. 바로 테이블에 문제의 해가 저장되어 있는지의 여부를 검사하는 내용이다.

ll DFS(int i, int remainingTime) {
    if (remainingTime < 0)
        return -INF;

    if (i == N)
        return 0;

    if (table[i][remainingTime] != -INF)	// 추가 종료 조건
        return table[i][remainingTime];
...

만약 해당 종료 조건을 통과하지 않는다면 아직 테이블에 해가 저장되어 있지 않은 것이다. 이제 기존의 코드를 다음과 같이 바꾼다.

ll DFS(int i, int remainingTime) {
    if (remainingTime < 0)
        return -INF;

    if (i == N)
        return 0;

    if (table[i][remainingTime] != -INF)
        return table[i][remainingTime];

    ll& ret = table[i][remainingTime];
    ret = max(
        DFS(i + 1, remainingTime - interval[i].walkCost) + interval[i].walkMoney,
        DFS(i + 1, remainingTime - interval[i].bicycleCost) + interval[i].bicycleMoney
    );
    
    return ret;
}

기존에는 ret을 ll type으로 선언했지만, ll& type으로 선언함으로써 테이블을 참조하도록 하였다. 이제 똑같이 재귀 함수를 사용해 ret에 최대 모금액을 저장하게 한 후 반환하면 끝이다.

DP result

제약 조건이 없는 상황에서도 잘 통과한 것을 확인할 수 있다.

전체 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define INF 100000000

class Interval {
    public:
        int walkCost;
        int walkMoney;
        int bicycleCost;
        int bicycleMoney;
};

int N, K;
vector<Interval> interval;
vector<vector<ll>> table;       // [curr interval][remaining time]

ll DFS(int i, int remainingTime);

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K;
    interval.resize(N);
    for (int i = 0; i < N; i++)
        cin >> interval[i].walkCost >> interval[i].walkMoney >> interval[i].bicycleCost >> interval[i].bicycleMoney;
    table.resize(N, vector<ll>(K + 1, -INF));
    
    cout << DFS(0, K);

    return 0;
}

ll DFS(int i, int remainingTime) {
    if (remainingTime < 0)
        return -INF;

    if (i == N)
        return 0;

    if (table[i][remainingTime] != -INF)
        return table[i][remainingTime];

    ll& ret = table[i][remainingTime];
    ret = max(
        DFS(i + 1, remainingTime - interval[i].walkCost) + interval[i].walkMoney,
        DFS(i + 1, remainingTime - interval[i].bicycleCost) + interval[i].bicycleMoney
    );
    
    return ret;
}

정리

마지막으로 앞서 설명한 완전탐색이 필요한 문제에 대한 Backtracking 로직을 DP 로직으로 바꾸는 과정을 나열하고 마무리하겠다.

  1. Backtracking 로직을 작성한다: 주의할 점은 문제에서 다루고 있는 상태 값을 전역 변수가 아닌 함수의 매개변수, 반환 값만으로 다루어야 한다는 것이다.
  2. 재귀 함수의 매개변수를 인덱스로 하고 반환 값을 저장하는 테이블을 생성한다: 이 과정은 DP 방법론에서 가장 까다로운 점화식을 찾는 단계에 해당하는데, 앞서 문제 없는 로직을 구현했다면 점화식이 즉시 완성된다.
  3. 기존의 재귀 함수에 종료 조건을 추가하고, 반환 값을 테이블의 값으로 교체한다: 테이블에 초기 값 외의 값이 저장되어 있는지 확인하고(즉, 문제가 이미 해결되었는지 확인하고), 기존에 재귀 함수의 지역 변수로 존재했던 반환 값을 테이블에 대한 참조로 교체한다.
profile
YUSHIN KIM
안녕하세요
다음 포스트

[Algorithm] 백준 1700번: 멀티탭 스케줄링

0개의 댓글