[알고리즘] 동적 계획법(Dynamic Programming, DP) 알아보기 ( 백준 24416번 피보나치 수-1 with 자바 )

 

 

🤔 동적 계획법 DP?

복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다.

즉, 문제 해결을 위해 설계하는 방법이나 접근 방식을 말합니다.

 

💡 메모이제이션(Memoization)

동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

wikipedia

동적 계획법(DP)의 핵심이 되는 기술로 가장 큰 특징이라고 할 수 있습니다.

상향식, 하향식 접근 방식을 통해 문제를 작은 하위 문제로 나누어 이를 해결하면서 하위 문제의 결과를 메모이제이션 즉 메모리에 저장함으로써 중복 연산을 줄일 수 있습니다.

 

🔎 상향식(bottom-up) 접근

작은 하위 문제들부터 시작하여 그 결과를 저장하고, 이를 이용하여 점진적으로 큰 문제의 답을 구해나가는 접근 방식입니다.

 

🔎 하향식(top-down) 접근

재귀 호출을 이용하여 문제를 해결할 때 주로 쓰입니다.

즉, 큰 문제를 작은 하위 문제로 나누어 해결하는 접근 방식입니다.

 

 

✔ 동적 계획법(DP) 적용 조건

🔎 중복되는 부분 문제 (Overlapping Subproblems)

DP는 문제를 작은 하위 문제로 나누고, 작은 문제의 결과를 재사용하여 원하는 결과를 도출하는 과정이라고 할 수 있습니다.

따라서 작은 문제를 해결하기 위해 동일한 작은 부분 문제가 반복적으로 발생하는 경우 DP를 적용할 수 있습니다.

 

🔎 최적 부분 구조 (Optimal Substructure)

주어진 문제의 최적의 답이 하위 문제의 최적의 답을 통해 얻어질 수 있는 경우를 말합니다.

 

👀 Example

public static int fibonacci(int n ){
    if( n == 1 || n == 2){
        return 1;
    }

    return fibonacci(n-1) + fibonacci(n - 2);

}

 

위 코드는 피보나치 수를 재귀 호출을 통해 구현해 보았습니다.

피보나치 수열은 이전 두 숫자의 합을 다음 숫자로 나타내는 수열입니다.

다음 숫자를 알아내려면 이전 숫자들의 합을 알아야 합니다 이 과정에서 그림처럼 중복되는 연산 즉, 중복되는 부분 문제가 발생한다는 걸 알 수 있습니다.

또한 전체 문제(fibonacci(5))의 답을 부분 문제들의 답을 통해 얻어질 수 있기 때문에 최적 부분 구조라고 할 수 있습니다.

두 조건을 만족함으로 피보나치 수를 구하기 위해서 DP방법론을 적용해 볼 .

 

 

✔ DP 문제

난이도 : 브론즈 1 🥉

백준 24416번 피보나치 수 1

24416번: 알고리즘 수업 - 피보나치 수 1

 

n의 피보나치 수를 재귀 호출과 DP를 통해 구하는 알고리즘을 비교하기 위해 각 코드가 몇 번 호출되는지 호출 횟수를 출력하는 문제입니다.

 

DP방법론을 적용한 코드입니다.

bottom-up 접근을 통해 작은 문제 즉, 피보나치 수의 첫번째 수, 두 번째 수 연산을 시작으로 결괏값을 저장하면서 저장한 결괏값을 통해 중복 연산을 줄이고 점차 n번째 수까지 값을 도출해 내는 과정으로 진행합니다.

DP의 핵심인 메모이제이션을 통해서 이전 값들을 저장하여 중복 연산을 제거하기 위해 배열 fibArr을 사용합니다.

static void fibonacci(int n ){
	// 피보나치 수의 첫번째와 두번째는 1이기 때문에 1로 설정해 줍니다.
    fibArr[0] = 1;
    fibArr[1] = 1;

    for( int i = 2; i<n; i++){
        fibArr[i] = fibArr[i-1] + fibArr[i-2];
        cnt++;
    }
}

 

📌

문제에서는 호출 횟수를 묻고 있기 때문에 cnt를 출력하지만 n번째의 피보나치 수를 출력해야 한다면 fibArr[n-1]을 통해 얻을 수 있습니다. ( n=5 일 때 fibArr = { 1, 1, 2, 3, 5 } )

또한 문제의 범위가 n(5<= n <= 40)이기 때문에 상관없지만 만약 범위가 1부터 시작이라면 ArrayIndexOutOfBoundsException이 발생할 수 있기 때문에 최대 범위로 메모이제이션 할 배열을 선언해주면 해결할 수 있습니다. ( fibArr = new int[최대범위] )

 

🔎 전체 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.StringBuilder;

public class Main{
    
    static int n, cnt;
    static int[] fibArr;
    
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine());
        fibArr = new int[n];
        
        cnt = 0;
        fib(n);
        sb.append(cnt).append(" ");
        
        cnt = 0;
        fibonacci(n);
        sb.append(cnt);
        
        System.out.print(sb);
        br.close();
	}
    
    static int fib(int n){
        if( n == 1 || n == 2){
            cnt++;
            return 1;
        } else {
            return fib(n -1) + fib(n - 2);
        }
    }
    
    static void fibonacci(int n ){
        fibArr[0] = 1;
        fibArr[1] = 1;
        
        for( int i = 2; i<n; i++){
            fibArr[i] = fibArr[i-1] + fibArr[i-2];
            cnt++;
        }
    }
}

 

 

 

---

 

 

📚 Reference : https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming