[알고리즘] DP(다이나믹 프로그래밍)

무1민·2023년 3월 15일
2

알고리즘 설명

목록 보기
1/6
post-thumbnail

📌개요

수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법 이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.


🔎사용 조건

1. 최적 부분 구조

큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우

2. 중복되는 부분 문제

동일한 작은 문제를 반복적으로 해결해야 하는 경우


🤷‍♂️DP를 쓰는 이유

일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산될 수 있다는 것이다.

예를 들어 피보나치 수열을 보면, 재귀로 구현했을 때 식은 간단하다.
return f(n) = f(n-1)+ f(n-2);
그런데 f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 구하기 때문에 반복되는 계산을 하게 된다.

그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용하면 중복된 계산은 다시 반복할 필요가 없다.


🙅‍♂️분할정복과의 차이

결정적인 차이점은 작은 문제가 중복이 일어나는지 안 일어나는지 이다.

분할정복은 큰 문제를 작은 문제로 나눴지만 작은 문제에서 반복이 일어나는 부분이 없다.
반면, DP는 작은 부분문제들이 반복되는 것을 이용해 답을 풀어나가는 방법이다.


👊탑다운(Top-Down) vs 바텀업(Bottom-Up)

DP문제를 푸는 방법은 탑다운과 바텀업이 있다.

두 방법 모두 큰 문제를 여러 개의 부분 문제들로 나누어 풀지만, 차이점이 존재한다.

🔻탑 다운(Top-Down)

  • 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
  • 하향식
  • 점화식을 이해하기 쉬운 장점
  • 가장 먼저 호출하는 문제는 가장 큰 문제
  • 일반적으로 재귀를 사용하는 구조는 같지만, 부분 문제에서 구한 값을 기억하면서 다음 재귀에서 재활용하는 과정을 추가해주면 된다.
import java.util.Scanner;
public class FibonacciNumber_TopDown {
	static long[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp = new long[n + 1];
		System.out.println(Fibonacci(n));
		sc.close();
	}
	private static long Fibonacci(int n) {
    	// 기저 조건(피보나치 수열의 초항).
		if (n == 1 || n == 2) {
			return dp[n] = 1;
		}
        // 만일, 저장된 값이 존재하는 경우 기억된 값을 바로 넘겨준다.
		if (dp[n] != 0) {
			return dp[n];
		}
        // 그렇지 않은 경우, 기저 조건까지 내려가서 구해진 값을 저장하면서 재귀를 전이한다.
		else {
			return dp[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
		}
	}
}


🔺바텀 업(Bottom-Up)

  • 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식
  • 상향식
  • 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있는 장점
  • 가장 작은 문제(기저 문제)부터 시작하여, 작은 문제를 해결하여 그 값을 저장하고, 다음 문제를 순차적으로 해결하며 전체 문제까지 해결하는 구현 방식
import java.util.Scanner;
public class FibonacciNumber_BottomUp {
	static long[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp = new long[n + 1];
		// 기저 조건을 바탕으로 초항을 먼저 초기화 해둔다.
		dp[1] = 1;
		dp[2] = 1;
		System.out.println(Fibonacci(n));
		sc.close();
	}
	private static long Fibonacci(int n) {
		// 기저 조건을 기반으로 테이블을 채워나간다(Tabulation).
		for(int i = 3; i <= n; i++) {
			// 점화식을 이용하여 쉽게 구할 수 있다.
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}
}

profile
야호

0개의 댓글