[Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기

동적 계획법 DP란❓

 

동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다.
 
주로 줄여서 DP라고 많이 말하며, 주어진 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 동일한 문제가 나왔을 시 저장해둔 결과를 재사용함으로써 전체 문제를 효율적으로 해결하는 기법입니다.
 
위 말을 기준으로 핵심을 뽑아보자면 다음과 같습니다.

• 하나의 큰 문제를 여러 개의 작은 문제로 나누어 결과 저장
• 동일 결과 재사용

 

DP 문제 성립 조건

동적 계획법(DP)는 두 가지 주요 원리인 "최적 구분 구조"와 "중복되는 하위 문제"를 기반으로 합니다.
 

• 최적 부분 구조(Optimal Substructure)
  • 문제의 최적 해가 하위 문제의 최적 해로 구성되는 성질입니다.
  • 즉, 큰 문제를 작은 하위 문제로 나누어 각 하위 문제의 최적 해를 구한 뒤, 이들을 결합하여 전체 문제의 최적 해를 구할 수 있는 경우입니다.
• 중복되는 하위 문제(Overlapping Subproblems)
  • 동일한 작은 문제가 여러 번 반복해서 계산되는 성질입니다.
  • 동적 계획법은 이러한 중복 계산을 피하기 위해 하위 문제의 결과를 저장(memoization)하고 재사용합니다.

최적해(Optimal Solution)는 최적화 문제에서 요구되는 목표를 가장 잘 달성하는 해를 의미

 

 

대표 DP 사례 : 피보나치 수열

피보나치수열은 대표적인 동적 프로그래밍의 사례입니다.
 
피보나치수열을 보면 DP와 비슷하는데 피보나치수열과 DP의 차이점은 재사용입니다.
 

public class Fibonacci {
	public static void main(String[] args) {
		int input = 6;
		
        System.out.println(fibo(input));
     }
     
     public static int fibo(int n) {
     	if (n <= 1) return n;
     	else return fibo(n-2) + fibo(n-1);
     }
}

// 결과 : 8

 
숫자가 작을 때는 차이는 없지만 숫자가 커지면 속도가 심각하게 저하됩니다. 만약 위 코드에서 input이 40이어도 시간이 걸리는 게 눈에 보이고 만약 100이라면 정말 오래 걸릴 것입니다.

 

 
왜냐면 위 그림을 보면 알 수 있듯이 피보나치수열은 재귀적으로 계속해서 들어가기 때문에 중복호출이라는 문제를 안고 있기 때문입니다. 따라서 숫자가 크면 클수록 중복되는 문제가 많아지게 됩니다.
 
이러한 문제를 해결하기 위해서 동적 프로그래밍을 구현해야 합니다.
 

동적 계획법 유형

동적 계획법은 주로 두 가지 접근 방식으로 구현됩니다. Top-Down과 Bottom-up

Top-down(하향식)

public class Topdown {
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		System.out.println(fibo(n));
		
	}
	
    // Top-down
	static int fibo(int x) {
		if( x ==1 || x==2) return 1;
		if(dp[x] != 0) return dp[x];
		dp[x] = fibo(x-1) + fibo(x-2);
		return dp[x];
	}
}

 
메모이제이션(Memoization)

• 상향식(Top-Down) 접근 방식으로, 재귀를 사용하여 문제를 해결합니다.
• 전체 문제부터 시작하여 가장 작은 문제까지 호출한 뒤, 계산된 하위 문제의 결과를 저장하여 재사용함으로써 중복 계산을 피합니다.
• 재귀 호출이 많아질 경우 스택 오버플로우가 발생할 수 있지만, 메모리 사용량을 줄일 수 있습니다.

Bottom-up(향식)

public class Bottomup {

	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		
		System.out.println(fibo(n));
	}
	
    // Bottom-up
	static int fibo(int x) {
		dp[1] =1;
		dp[2] =1;
		for(int i=3; i<x+1; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[x];
	}
}

 
타불레이션(Tabulation)

• 하향식(Bottom-Up) 접근 방식으로, 반복문을 사용하여 문제를 해결합니다.
• 작은 하위 문제부터 시작하여 결과를 저장(Tabulation)한 뒤, 이 값들을 사용하여 다음 문제를 순차적으로 해결하며 전체 문제까지 해결하는 구현 방
• 일반적으로 메모리 사용량이 크지만, 호출 스택을 사용하지 않아 스택 오버플로우의 위험이 없습니다.

 

메모이제이션 memoizaion 특징

메모이제이션(memoization)은 동적 계획법의 핵심 기법 중 하나입니다. 핵심 기법이기 때문에 좀 더 자세히 살펴보면 앞서 말했듯이 재귀 알고리즘의 중복 계산을 피하기 위해서 이미 계산된 값을 저장하고 재사용하는 방법입니다.
 
메모이제이션의 특징은 다음과 같습니다.

 

•  중복 계산 제거
  • 재귀적 접근에서 발생하는 동일한 함수 호출을 피하기 위해 이전에 계산한 결과를 저장하여 재사용합니다.
• 캐싱
  • 이미 계산된 결과를 저장하고 저장된 값은 필요할 때 바로 반환되므로 시간 복잡도가 크게 줄어듭니다.
• 시간 복잡도 개선
  • 메모이제이션을 사용하면 많은 재귀적 호출을 제거하여 시간 복잡도를 대폭 줄일 수 있습니다.
    예를 들어, 피보나치수열의 경우 단순 재귀의 지수 시간 복잡도 O(2^n)을 선형 시간 복잡도 O(n)으로 줄일 수 있습니다.