[알고리즘] 동적 계획법

알고리즘

[알고리즘] 동적 계획법

라임온조 2023. 5. 25. 10:30

1. 개념

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

2. 특징

큰 문제를 작은 문제로 나눌 수 있어야 한다
작은 문제들이 반복되고, 작은 문제들의 결과값은 항상 같아야 한다.
작은 문제들은 한 번만 계산해 DP 테이블에 저장한다. 이후에 재사용할 때는 DP 테이블에 있는 것을 사용한다. 이는 메모이제이션 기법이다.
톱 다운 방식과 바텀 업 방식으로 구현 가능하다

3. 원리

피보나치 수열을 통해 원리를 알아보자.

피보나치 수열 공식: D[N] = D[N-1] + D[N-2]

1) 동적 계획법으로 풀 수 있는지 확인하기

피보나치 수열의 3번째 값은 1번째 값과 2번째 값의 합이다. 그리고 이는 수열이 진행되면서 반복된다. 즉 큰 문제를 작은 문제로 나눌 수 있고 작은 문제들이 반복되며, 수열의 값은 변하지 않기 때문에 작은 문제들의 결과값은 항상 같다.

따라서, 동적 계획법으로 풀 수 있다.

2) 점화식 세우기

작은 문제 하나를 풀 수 있도록 하는 식을 세워야 한다. 피보나치 수열의 경우 피보나치 수열 공식이 점화식이 된다.

3) 메모이제이션 원리 사용하기

메모이제이션은 부분 문제를 풀었을 때 이 값을 테이블에 저장해 놓고, 다음에 같은 부분 문제를 풀 필요가 있을 때 계산을 하지 않고 테이블에 저장된 값을 사용하는 원리를 말한다.

이러한 방식은 불필요한 연산과 탐색을 줄여 시간 복잡도 측면에서 이점이 된다.

4) 톱 다운이나 바텀 업 방식 사용하기

① 톱 다운

위에서부터 문제를 파악해서 내려오는 방식이다.
재귀함수로 구현한다.
코드 가독성이 좋다.
이해하기 편하다
재귀의 깊이가 깊어지면 런타임 에러가 발생할 수 있다.

② 바텀 업

가장 작은 문제부터 문제를 해결하면서 큰 문제로 확장해 나가는 방식이다.
반복문의 형태로 구현한다
톱 다운보다 안전하다.

4. 코드

1) 톱 다운

 // 입력 받기
   Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    // D 배열 초기화
    D = new int[n+1];
    for(int i = 0; i<= n; i++){
        D[i] = -1;
    }
    D[0] = 0;
    D[1] = 1;

    // 답 구하기
    fibo(n);

    // 답 출력
    System.out.println(D[n]);



}

public static int fibo(int n){
    if(D[n] != -1){
        return D[n];
    }
    return D[n] = fibo(n-2) + fibo(n-1); // 구한 값을 바로 리턴하지 않고 DP 테이블에 저장한 후 리턴하도록 구현
}