[Java] DP : Top-down과 Bottom-up

9north·2024년 9월 8일

DP는 각종 기업 코딩 테스트에서 주의깊게 다루어지는 중요한 알고리즘 기법이다. DP의 정의와 함께, DP를 처리하는 두 가지 방식인 Top-down 접근법과 Bottom-up 접근법에 대해 알아보고, 효율적인 최적화 방안을 생각해보자.

DP(Dynamic Programing)

DP 알고리즘은 그리디 알고리즘과 같이, 최적화 문제를 해결하는 알고리즘이다. 문제를 해결할 때, 먼저 작은 부분 문제들의 해를 구하고 이를 이용하여 보다 큰 크기의 부분 문제를 해결해 나가며, 최종적으로 원래 주어진 문제를 해결한다.
DP는 귀납법을 만족하는 점화식을 찾아서, 재귀 함수(recursive)와 메모이제이션(memoization)을 활용해 문제를 해결한다.

메모이제이션

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 중복 계산을 줄여 전체적인 실행 속도를 빠르게 하는 기술

DP 적용 가능 문제의 두 가지 필수 요건

1 최적 부분 문제 구조(Optimal substructure)

DP로 풀 수 있는 문제는, 최적화의 원칙(Principle of Optimality)을 만족해야 한다.

최적화의 원칙

어떤 문제에 대한 해가 최적일 때, 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다.

DP는 작은 해의 최적 해를 통해 큰 문제의 최적화를 구하기 때문에, 최적화의 원칙을 만족하는 문제가 아니라면 DP를 적용할 수 없다.

2 중복 부분 문제 구조(Overlapping subproblems)

중복 부분 문제 구조

문제가 여러 번 재사용 가능한 하위 문제로 분해되거나, 문제에 대한 재귀 알고리즘이 항상 새로운 하위 문제를 생성하는 대신 동일한 하위 문제를 계속 반복해서 해결하는 문제

DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용해 순환적으로 큰 문제를 해결한다. 순환 관계의 명시적 표현을 위해 점화식을 사용하며, 이전에 계산된 작은 문제의 해가 다른 문제에서 필요하게 된다.
이를 위해 이미 해결된 작은 문제들의 해들을 어떤 저장 공간에 저장한다. 메모이제이션 기법을 사용해 저장된 작은 문제들의 해는, 필요할 때마다 다시 계산하는 과정 없이 참조할 수 있기 때문에 중복된 계산을 피하게 만들어준다.

Top-down approach

재귀 함수가 직접적인 결과를 리턴한다. 모든 문제의 해가 하위 문제의 해를 사용하여 재귀적으로 공식화될 수 있고, 하위 문제가 중복인 경우, 하위 문제의 해결책을 쉽게 메모이제이션할 수 있다. 새로운 하위 문제를 풀려고 할 때마다 먼저 표를 확인하여 이미 풀렸는지 확인한다. 해가 있으면 사용하고, 없으면 하위문제를 풀고 그 해를 다시 기록한다.

장점

논리적으로 문제를 구성하기 쉽다.
직관적 코드 작성이 가능하다.
재귀 트리에서 불필요한 계산을 피할 수 있다.

단점

재귀 호출로 인해 함수 호출 스택이 깊어지면, 스택 오버플로우 위험이 있다.
큰 입력에 대해 효율적으로 동작하지 않는다면, 재귀의 오버 헤드가 비효율적으로 작용한다.

최적화 방안

가지치기
메모이제이션
최대 재귀 깊이 조정

백준 1463번 1로 만들기로 드는 예시

import java.io.*;
import java.util.*;

public class Main{
    
    public static int d[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());
        d = new int[number+1];
        System.out.println(calculate(number));
    }

    public static int calculate(int number){
        if (number == 1){
            return 0;
        }
        if (d[number] > 0){
            return d[number];
        }
        d[number] = calculate(number-1) + 1;
        if (number%3 == 0) {
            d[number] = Math.min(d[number],calculate(number/3) +1);
        }
        if (number%2 == 0) {
            d[number] = Math.min(d[number],calculate(number/2) +1);
        }
        return d[number];
    }
}

Bottom-up approach

하위 문제의 관점에서 재귀적으로 공식화하면 Bottom-up 방식으로 문제를 재구성할 수 있다. 즉, 하위 문제를 먼저 풀고 그 해를 사용하여 더 큰 하위 문제에 대한 해에 도달한다. 이는 일반적으로 작은 하위 문제에 대한 해를 사용하여 점점 더 큰 하위 문제에 대한 해를 반복적으로 생성하여 최종해에 도달한다. 예를 들어, 피보나치 함수 F(x) 의 경우, F(41)과 F(42)가 있으면 F(43)에 도달할 수 있다.

장점

함수 호출 스택 부담 X
메모리 오버헤드 줄어듦
하위 문제를 순차적으로 해결하므로 메모리 접근이 국소적

단점

모든 하위 문제를 계산해야 하므로, 불필요한 계산 발생함
DP 테이블을 미리 만들어야 해 메모리 사용량이 클 수 있음
비직관적, 구현의 어려움

최적화 방안

필요한 값만 테이블에 저장해 메모리 사용량 줄임
더 이상 필요하지 않는 값은 제거하거나 덮어씌워 공간 복잡도 개선
하위 문제 간의 의존성을 고려해 계산 순서를 최적화

백준 1463번 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));
       int number = Integer.parseInt(br.readLine());
       int dp[] = new int[number+1];
       dp[0] = 0;
       dp[1] = 0;
       for (int i = 2; i <= number; i++){
           dp[i] = dp[i-1] + 1;
           if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
           if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
       }
       System.out.println(dp[number]);
       br.close();
       
    }
}