Java: 동적 계획법(Dynamic Programming) 개념과 이해

 

동적 계획법

Dynamic Programming 또는 DP라고 부른다

 

1940년대 리차드 벨만이 사용하던 용어이다.

어떤 문제가 주어질 때 본래의 문제를 분석하고 반복되는 연산을 찾아낸다

연산을 기준으로 문제를 작은 문제들로 나눈 다음

각 문제들의 결과값을 기록하며 본래의 문제의 해답을 구하는 방법이다

 

단계를 구체화하면 다음과 같다

문제 ➡ 점화식 발견 ➡ 작은 문제들로 나누기 ➡ 각 문제의 해답을 기록 ➡ 해답

 

 

피보나치 수열

피보나치 수열을 통해 동적계획법을 이해한다

 

점화식 발견, 연산한 값을 기록하는 것이

dp의 핵심이라 볼 수 있다

 

피보나치 수열의 0항과 1항은 1이고 n항은 다음과 같이 표현된다

f(n) = f(n-1) + f(n-2)

 

dp를 사용하지 않고 피보나치 특정항을 구해보자

40항을 구하려고 한다. 반복문 or 메소드를 사용하면

컴퓨터는 아래처럼 연산할 것이다

1 1 2 3 5 8 13 21 34 ...

뚜루루...40항은 165580141

 

근데 갑자기 41항을 또 구하고 싶어졌다

컴퓨터는 또 처음부터 연산한다

1 1 2 3 5 8 13 21 34 ...

위 경우 비효율적으로 연산을 반복한다

 

동적 계획법을 통해 피보나치 수열을 구해보자

1) 값을 기록하기 위해 dp[ ] 배열을 만든다

2) n항의 값을 배열 안에 기록한다

3) 기록된 n항과 n-1항을 토대로 n+1항을 구한다

4) while문 안에서 피보나치의 여러 항을 구할 수 있다

import java.util.Scanner;
public class Main {
	static Integer[]dp = new Integer[42]; //null을 사용하기 위해  Integer을 사용한다

	static Integer fibonacci(int N) {
	
		if(dp[N]==null) { //값이 비어있는 경우에만 연산을 한다
		
			dp[N]= fibonacci(N-1) + fibonacci(N-2);//연산 후 배열 안에 저장한다
	
		}
		
		return dp[N]; //dp[N]값을 반환한다
	}
	
public static void main(String[] args){
	 Scanner sc = new Scanner(System.in);
	 dp[0] = 1; //0항을 넣어준다
	 dp[1] = 1; //1항을 넣어준다
	 
	 while(true) { //while문 안에서 여러 번 피보나치 해를 구한다
		 int N = sc.nextInt();
		 System.out.println(fibonacci(N));
	 }

}}

*배열을 통해 연산 중간 중간을 기록하면 피보나치 수열을 구할 때 매번 재연산할 필요가 없어진다

 

 

동적 계획법의 구현

연산의 방향에 따라 동적 계획법의 구현 방법이 나눠진다

 

메모이제이션(Memoization)

위처럼 동일한 문제를 반복할 때 이미 계산을 마친 값들을

저장하고 활용하는 방식을 메모이제이션이라고 한다.

동적 계획법을 구현시 핵심적인 요소이다

 

Top-Down

메소드의 재귀를 이용해 풀이하는 방식

 

위의 경우처럼 피보나치 메소드(N)를 만들고

return값으로 자기 자신의 메소드(N-1)을 호출한다.

호출한 메소드(N-1)은 연쇄적으로 메소드를 호출하게 된다

이미 연산을 마친 후 배열에 기록되어있다면 재연산하지 않도록 한다

메소드 특성상 유지보수가 Bottom-Up보다 용이하다

static Integer fibonacci(int N) {
	
		if(dp[N]==null) { //값이 비어있는 경우에만 연산을 한다
		
			dp[N]= fibonacci(N-1) + fibonacci(N-2);//연산 후 배열 안에 저장한다
	
		}
		
		return dp[N]; //dp[N]값을 반환한다
	}

 

 

Bottom-Up

반복문을 통해 i의 0부터 N(또는 N-1)까지 연산한다

메소드를 만들지 않고 반복문을 활용해

연산의 결과값을 누적해간다.

코드길이나 논리가 Top-Bottom에 비해 단순하다

import java.util.Scanner;
public class Main {
	static Integer[]dp = new Integer[42]; //null을 사용하기 위해  Integer을 사용한다
public static void main(String[] args){
	 Scanner sc = new Scanner(System.in);
	 dp[0] = 1; //0항을 넣어준다
	 dp[1] = 1; //1항을 넣어준다
	 
	 while(true) { //while문 안에서 여러 번 피보나치 해를 구한다
		 int N = sc.nextInt();
		 
		 for(int i=0; i<=N; i++) {
			 if(dp[i]==null) {  //배열에 값이 없을 때만 연산한다
				 dp[i]=dp[i-1]+dp[i-2];
			 }
		 }
		 System.out.println(dp[N]);
	 }

}}

 

 

 

동적 계획법 대표 유형

 

LIS

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.(최대길이 1,000)

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은

A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중

가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. (최대 1,000자)

 

부분수열 최대합

계단 오르는 데는 다음과 같은 규칙이 있다.

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다.

하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나,

첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다. 각 계단에 쓰여 있는 점수가 주어질 때

이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면

총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

 

Knapsack