[Java]동적 계획법(Dynamic Programming)

*동적 계획법(Dynamic Programming)

->동적 계획법이란 특정 범위까지의 최적해(상위 문제)를 구하기 위하여 다른 범위까지의 최적해(하위 문제)를 이용하여 효율적으로 해를 구하는 알고리즘 설계 기법이다.

->쉽게 말해, 이전에 구한 값을 기반으로 규칙성을 파악하여 다음 값을 구하는 것이라고 생각하면 된다.

->알고리즘 설계 기법(패러다임) 중 하나이다. 하위 문제의 최적해를 적절히 사용하여 상위 문제를 해결함으로써, 불필요한 계산을 줄일 수 있다.

※ 어떤 문제를 해결할 때, 기본적인 방법은 모든 경우의 수를 고려하는 것(완전 탐색)이다. 어떤 문제를 해결할 때, 그 문제에 대한 모든 경우의 수를 고려할 수 있는 설계가 가능하다면, 그 문제는 시간과 자원이 매우 많이 들지는 몰라도 언젠가 반드시 정확한 결과를 도출할 것이다. 다만 시공간적 자원의 한계로 인하여 분할 정복, 그리디, 백트래킹 등과 같은 알고리즘 설계 기법이 등장한 것이고 동적 계획법 역시 그러한 한계를 해결하기 위해 설계된 알고리즘 패러다임인 것이다.

※ 동적 계획법(Dynamic Programming)이라는 이름은 딱히 해당 알고리즘의 패러다임을 이해하는데 직관적이지 않은 편이다. 동적 계획법의 고안자인 벨만이 연구소에서 펀딩을 받기 위해서 이름을 최대한 간지나게 지을려다보니 Dynamic이라는 용어를 사용하게 됐다고 한다.

(참고 : https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95#toc)

 

*적용 가능한 문제

->동적 계획법은 아래 두 조건을 만족하는 경우 해당 패러다임을 적용하여 문제를 해결하는데 유용하다고 알려져있다.

 

(1) 최적 부분 문제 구조(Optimal Substructure)

->쉽게 말해 앞서 정의한 바와 같이 이전에 구한 최적해(부분 문제)를 바탕으로 다음 문제의 최적해(전체 문제)를 구할 수 있는 구조여야 한다는 것이다.

->다시 말해 부분 문제가 전체 문제의 최적해라는 보장이 있는 구조를 최적 부분 문제 구조라고 생각하면 된다.

 

※ 최적 부분 문제 구조를 갖는 경우 : 최적 부분 문제 구조를 갖는 경우는 대표적으로 어떤 경유지를 거쳐서 목적지로 가는 문제가 있다. 아래 그림을 보자.

 그림에서 서울에서 부산으로 가는 최단 경로를 구하는 문제(전체 문제)를 생각해보자. 그런데 그림에서 서울에서 부산으로 가는 최단 경로는 서울에서 대전으로 가는 최단 경로(부분 문제)와 서울에서 부산으로가는 최단 경로(부분 문제이자 전체 문제)로 나누어 생각할 수 있다. 또한, 서울에서 대전으로가는 최단 경로 200km(최적해)는 이후 대전에서 부산으로가는 최단 경로 150km와(여기에서 150km는 최적해를 의미하지 않는다. 부분 문제의 해라고 보기 힘들기 때문이다) 적절히 조합하여 전체 문제를 해결 가능함을 알 수 있다. 

 

※ 최적 부분 문제 구조를 갖지 않는 경우 : 위 그림에서 조건을 몇가지 살짝 바꿔보자.

 그림에서 서울에서 부산으로 가는 최소 비용을 구하는 문제(전체 문제)를 생각해보자. 앞 선 문제와 비슷하지만, 여기에는 '서울에서 대전을 경유해서 바로 부산으로 가는 경우의 비용은 33000원'이라는 조건이 하나 더 추가 되었다. 이 조건으로 인해, 앞서 나누었던 부분 문제(서울에서 대전)는 전체 문제를 해결하는 최적해라는 보장이 사라져 버린다! 즉, 동적 계획법을 잘 활용하려면 부분 문제를 어떻게 설정해야지 최적 부분 문제 구조를 갖는지 잘 파악해야 함을 알 수 있다.

 

(2) 중복 부분 문제 구조(Overlapping Subproblems)

->말 그대로 부분 문제들이 반복되는 경향이 존재한다는 것을 의미한다. 쉽게 말해서 부분 문제를 분할해가는 과정에서, 그 각 상위 문제와 하위 문제의 관계가 반복되는 경향이 존재한다는 것을 의미한다.

->위의 예시를 바탕으로 아래 그림을 살펴보자.

 마찬가지로 서울에서 부산으로 가는 최단 경로(전체 문제)를 해결한다고 생각해보자. 그래서 우선 서울에서 대전으로 가는 최단경로(부분 문제)는 무엇일까?라는 질문을 출발하여 서울에서 경기로 가는 최단경로(최하위 부분 문제)는 무엇일까?라는 질문까지 내려갔다. 이 구조에서 부분 문제의 구조가 '각 위치 까지의 최단 경로는 무엇인가?'로 반복된다는 것을 알 수 있다. 그냥 쉽게 말해 이런 구조를 갖는 것이 중복 부분 문제 구조를 갖는다라고 이해해두면 된다.

※ 결국 이 그림이 동적 계획법의 사고 진행 과정이 어떤 방식으로 진행되는지 단편적으로 이해하는데 도움이 될 수 있을 것이다. 전체 문제를 부분 문제로 나누고, 그 부분 문제를 작은 문제부터 해결(서울에서 경기, 서울에서 대전, 서울에서 부산)해 나아가고, 각 단계에서 구한 해를 다음 문제에서 재사용함으로써 전체 문제를 해결하는 것을 확인할 수 있다.

 

*vs 분할 정복 패러다임

->동적 계획법과 분할 정복 패러다임 모두 전체 문제를 부분 문제로 나누어 생각한다는 점에서 그 차이점을 느끼기 어려울 수 있다. 이를 구분하기 가장 좋은 것은 동적 계획법은 부분 문제 사이에 연관성이 존재하고, 분할 정복은 부분 문제 사이에 연관성이 존재하지 않는다는 점을 이해하면 된다.

->예를 들어 병합 정렬(Merge Sort)을 생각해보자. 병합 정렬의 경우 모든 배열을 각각 분할(부분 문제)하고, 최종적으로 분할된 배열부터 각 배열을 합치며 정렬하는 과정을 반복(단순히 부분 문제를 큰 문제로 결합하며 해결)하는 것이다. 즉, 부분 문제 사이에 딱히 별 연관성이 없음을 알 수 있다.

 

*구현 방식

->동적 계획법은 특성상 Top-down 방식과 Bottom-up 방식으로 구현이 가능하다.

->사실 어떤 문제를 푸느냐에 따라서 Top-down 방식으로 구현하든 Bottom-up 방식으로 구현하든 각 방식이 압도적으로 우위를 가지는 장단점은 명확하지 않다고 한다. 따라서, 장단점의 경우에는 보통 이러하다더라~ 정도로 이해하면 좋을 것 같다.

 

(1) Top-down 구현 방식

->전체 문제부터 시작하여, 가장 작은 문제(기저 문제)까지 호출한 뒤, 작은 문제에서 해결한 값을 저장 및 기억(Memoization)하면서 해당 결과 값을 재활용하면서 문제를 해결하는 구현 방식을 말한다. 이러한 문제 해결의 특성상 재귀 호출을 사용하는 특징이 있다.

->재귀 호출을 사용하기 때문에 Stack Overflow 등의 문제가 발생할 수 있지만, 전체 문제부터 시작하여 작은 문제로 내려가는 직관적인 구조이기 때문에 이해하기 쉬운 장점이 존재한다.

 

(2) Bottom-up 구현 방식

->가장 작은 문제(기저 문제)부터 시작하여, 작은 문제를 해결하여 그 값을 저장(Tabulation)하고, 이 값들을 기반으로 다음 문제를 순차적으로 해결하며 전체 문제까지 해결하는 구현 방식을 말한다. 이러한 문제 해결의 특성상 반복문을 사용하는 특징이 있다.

->반복문을 사용하기 때문에 Top-down 방식에 비하여 효율성이 좋다고 알려져 있지만, 앞서 말한대로 문제 및 오버헤드, 설계에 따라서 Case by Case라고 한다. 또한 직관적인 구조가 아니기 때문에 구현이 어려울 수 있는 단점이 존재한다.

※ Tabulation? : Tabulation의 사전적 정의는 '도표 작성'이다. 문제 해결 방식이 표를 채워나가는 것과 유사하다고 하여 붙여진 이름이다. 따라서 Bottom-up방식을 사용하는 경우는 Memoization이라고 부르지 않고 Tabulation을 활용하여 값을 재활용한다고 이해하면 된다.

 

*피보나치 수열과 다이나믹 프로그래밍

->다이나믹 프로그래밍을 설명할 때, 가장 기본적이고 자주 사용되는 문제는 피보나치 수열의 값을 구하는 문제이다.

 

(1) 피보나치 수열이란?

->첫째 항과 둘째 항이 1의 값을 가지고, 그 뒤의 모든 항은 바로 앞 두 항의 합으로 구성된 수열을 말한다. 예를 들면, 다음과 피보나치 수열은 다음과 같이 진행된다. 1, 1, 2, 3, 5, 8, 13, 21...

->즉, 피보나치 수열을 Fn이라고 한다면, 피보나치 수열은 다음과 같이 수학적으로 정의할 수 있다.

 

(2) 피보나치 수열의 일반항의 값을 구하는 프로그램을 작성해보자(단순 재귀 호출).

->재귀를 사용하면, 피보나치 수열을 구하는 일반적인 프로그램을 작성하는 것은 쉽다. 코드로 작성하면 아래와 같을 것이다.

import java.util.Scanner;

public class FibonacciNumber {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		// n번째 피보나치 수를 구하고 출력하라.
		System.out.println(Fibonacci(n));
		sc.close();
	}

	private static long Fibonacci(int n) {
		// 기저 조건(피보나치 수열의 초항).
		if(n == 1 || n == 2) {
			return 1;
		}
		// 점화식.
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}
}

->하지만 해당 프로그램은 효율적으로 동작할까? 당장 100만 입력해봐도 결과를 도출하는데 매우 오랜 시간이 걸릴 것임을 알 수 있다. 그 이유는 아래 호출 구조를 보면서 파악해보자.

일반적인 재귀를 사용한 경우 재귀 호출 구조도와 반복되는 부분 확인

 그림과 같이 호출이 반복될 때 마다, 이미 구했던 값임에도 불구하고 다음 재귀에서 반복해서 재귀 호출이 발생하는 것을 확인할 수 있다. 이 경우 시간 복잡도는 O(2^N)이라고 한다. 즉, 연산의 횟수가 N이 늘어남에 따라 지수배 만큼 늘어나기 때문에 효율적인 구현이라고 볼 수 없다.

 

(3) Top-down 구현 방식으로 피보나치 수열의 일반항의 값을 구해보자.

->이제 앞에서 학습한 다이나믹 프로그래밍의 구현 방식 중 하나인 Top-down 구현 방식을 활용하여 코드를 작성해보자. 일반적으로 재귀를 사용하는 구조는 같지만, 부분 문제에서 구한 값을 기억(Memoization)하면서 다음 재귀에서 재활용하는 과정을 추가해주면 된다.

import java.util.Scanner;

public class FibonacciNumber_TopDown {
	// Memoization을 적용할 배열.
	static long[] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp = new long[n + 1];

		// n번째 피보나치 수를 구하고 출력하라.
		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);
		}
	}
}

->이렇게 부분 문제에서 해결한 값을 저장(Memoization)하면서 문제를 해결하는 경우 불필요한 계산 과정을 줄여주기 때문에 엄청난 속도 향상을 보임을 알 수 있다! 이 경우 시간 복잡도는 O(N)을 갖는다고 한다. 아래 호출 구조를 참고해보자.

값을 그때마다 기억하고, 적절하게 호출하면서 불 필요한 계산 과정을 줄일 수 있다!

 

(4) Top-down 구현 방식으로 피보나치 수열의 일반항의 값을 구해보자.

->그럼 이번에는 앞에서 학습한 다이나믹 프로그래밍의 구현 방식 중 다른 하나인 Bottom-down 구현 방식을 활용하여 코드를 작성해보자. Bottom-up 구현 방식은 가장 작은 문제(기저 문제)부터 시작하여, 작은 문제를 해결하여 그 값을 저장(Tabulation)하고, 이 값들을 기반으로 다음 문제를 순차적으로 해결하며 전체 문제까지 해결하는 구현 방식이라고 하였다. 즉, 기저 조건(1항, 2항의 값은 1)을 기반으로 다음 값을 구하면서 테이블을 채워가는 방식으로 반복문을 구현하면 된다. 아래 코드를 참고하자.

import java.util.Scanner;

public class FibonacciNumber_BottomUp {
	// Tabulation을 적용할 배열.
	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;

		// n번째 피보나치 수를 구하고 출력하라.
		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];
	}
}

->마찬가지로 이렇게 부분 문제에서 해결한 값을 저장(Tabulation)하면서 문제를 해결하는 경우 불필요한 계산 과정을 줄여주기 때문에 엄청난 속도 향상을 보임을 알 수 있다! 이 경우 역시 시간 복잡도는 O(N)을 갖는다고 한다. 

※ 사실 Tabulation을 사용하지 않더라도 단순 반복문을 이용하여 피보나치수의 일반항의 값을 구할 수 있음을 알 수 있을 것이다. 즉, 굳이 값을 저장하지 않더라도 반복문을 적용한다면 앞의 두 값만 기억하고 있다면 굳이 메모리 공간을 낭비하지 않더라도 결과를 계산할 수 있다는 말이다. 다만 전체적인 과정의 값을 모두 기억해가며 풀어가는 방식이 동적 계획법의 정석이기 때문에 이렇게 소개한 것 뿐이고, 이 경우와 마찬가지로 데이터를 어떤 방식으로 기억할 지(단순히 변수에 담을지, n차원 배열에 담을지, 트리 자료구조에 담을지...)는 문제에 따르게 다르게 생각하면 된다. 실제로 데이터를 어떤 방식으로 저장할지를 생각하는 것이 동적 계획법의 출발이고, 알고리즘 실력을 가르는 중요한 요소임을 많은 문제 풀이를 하며 이해할 수 있을 것이다.

※ Top-down 방식과 달리 기저 조건부터 출발해 전체 문제를 해결하는 것을 확인할 수 있다. 이를 바탕으로 Top-down방식과 Bottom-up방식의 차이점을 이해할 수 있을 것이다.

 

*동적 계획법 문제 접근 방식

->해당 글을 잘 이해하였다면 동적 계획법은 이러하다..는 대략적인 느낌은 이해했을 것이라 생각한다. 다만, 실전 DP문제를 마주하면 나의 알고리즘 실력에 자괴감이 들때가 많을 것이다. 그 만큼 동적 계획법은 난이도가 있는 알고리즘 패러다임이고, 당연한 것이기 때문에... 꾸준히 연습하는 것 밖에 답이 없어보인다...

->다음은 일반적인 동적 계획법 문제 접근 방식이다. 물론 접근 방식을 알고 있다고해도 쉽게 적용하긴 힘들 것이다...

 

(1) 문제를 특정한 부분문제로 나누고, 해당 부분 문제의 최적해들을 저장할 dp 테이블을 정의해본다.

->이를 테면 앞의 서울에서 부산까지 가는 최단 경로를 구하는 예시를 기준으로 생각해보면, 'n번째 지역까지 가는데 필요한 최단 경로'라는 부분 문제를 생각해볼 수 있고, 이를 1차원 배열에 저장하면 되겠다는 생각을 해볼 수 있다.

->쉽게 말해 부분 문제를 무엇으로 둘거고, 그걸 어떻게 저장해볼까?를 생각하는 단계이다.

 

(2) 부분 문제의 관계를 생각하며 점화식을 도출한다.

->이를 테면 앞의 서울에서 부산까지 가는 최단 경로를 구하는 예시를 기준으로 생각해보면 'dp[n] = dp[n - 1] + (n - 1지역에서 n으로 가는 최단 거리)' 라는 점화식을 세울 수 있음을 알 수 있다.

->쉽게 말해 해당 부분 문제의 규칙성을 파악해보고, 점화식과 기저 조건을 정의하는 단계이다. 물론... 규칙성을 찾는것이 말 처럼 쉽지는 않을 것이다.

 

(3) 점화식을 바탕으로 dp 테이블을 갱신하면서 최종적으로 전체 문제를 해결한다.

->이를 테면 앞의 서울에서 부산까지 가는 최단 경로를 구하는 예시를 기준으로 생각해보면 결국 dp[n]의 값이 최종 답이 되는 것을 확인할 수 있다.

->사실 이 단계는 확인하는 단계이다. 데이터를 저장할 dp테이블 설계와 각 데이터간의 연관성을 바탕으로 점화식을 잘 정의하였다면 올바른 답이 도출되는 것을 확인할 수 있을 것이다.