『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

동적 계획법 (Dynamic Programming)

사실 모든 알고리즘 문제들은 완전 탐색을 이용해 정답을 도출할 수 있다. 단지 비효율적인 연산과 시간을 없애고, 답을 효율적으로 도출하기 위해 여러 알고리즘 기법이 생긴 것이다.

• 동적 계획법(DP)은 가장 광범위한 여러 유형의 문제를 논리적인 사고를 이용해 효율적으로 풀 수 있는 알고리즘이다.
• 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법이다.

핵심 이론

원리와 구현 방식

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.
   • 이를 메모이제이션(Memoization) 기법이라고 한다.
4. 동적 계획법은 Top-down 방식과 Bottom-up 방식으로 구현할 수 있다.

피보나치 수열

동적 계획법의 가장 대표적인 문제이다.

• 피보나치 수열의 공식은 다음과 같다.

1. 동적 계획법으로 풀 수 있는지 확인하기

   • N번째 피보나치 수열은 N-1번째 피보나치 수열과 N-2번째 피보나치 수열의 합이다.
   • 즉, N번째 피보나치 수열을 구하는 문제는 N-1번째 피보나치 수열과 N-2번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있다.
   • 수열의 값은 항상 같다.
   • 따라서 동적 계획법으로 풀 수 있다.

2. 점화식 세우기

   • 점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요하다.
   • 피보나치 수열의 점화식은 $D[i]=D[i-1]+D[i-2]$이 된다.

3. 메모이제이션 원리 이해하기

   • 메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것을 말한다.
   • 피보나치 수열은 맨 왼쪽 탐색 부분에서 최초로 값이 구해지고, 이때 DP 테이블에 값이 저장된다. 나중에 앞의 피보나치 수열의 값이 필요할 때 재연산을 이용해 구하지 않고, DP 테이블에서 바로 값을 추출한다.
   • 이러한 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측변에서 많은 이점을 가질 수 있다.

4. 톱-다운 구현 방식 이해하기

   • 말 그대로 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수를 사용해 코드를 구현한다.
   • 코드의 가독성이 좋고, 이해하기가 편하다는 장점이 있다.
   • 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있다.

   /**
   * Top-down 방식의 피보나치 수열
   */
   
   static int[] D;
   public static void main(String[] args) {
   	
   	Scanner sc = new Scanner(System.in);
   	int n = sc.nextInt();
   	
   	D = new int[n+1];
   	for(int i=0; i<=n; i++) {
   		D[i] = -1;
   	}
   	
   	D[0] = 0;
   	D[1] = 1;
   	fibo(n);
   	
   	System.out.println(D[n]);
   }
   
   static int fibo(int n) {
   	// 기존에 계산한 적이 있는 부분의 문제일 경우
   	if (D[n] != -1) {
   		return D[n];
   	}
   	// 메모이제이션: 구한 값을 바로 리턴하지 않고
   	// DP 테이블에 저장한 후 리턴하도록 구현
   	return D[n] = fibo(n-2) + fibo(n-1);
   }

5. 바텀-업 구현 방식 이해하기

   • 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식이다.
   • 주로 반복문의 형태로 구현한다.
   • 톱-다운 방식보다는 바텀-업 방식이 좀 더 안전한 방식이다.

   /**
   * Bottom-up 방식의 피보나치 수열
   */
   
   static int[] D;
   public static void main(String[] args) {
   	
   	Scanner sc = new Scanner(System.in);
   	int n = sc.nextInt();
   	
   	D = new int[n+1];
   	for(int i=0; i<=n; i++) {
   		D[i] = -1;
   	}
   	
   	D[0] = 0;
   	D[1] = 1;
   	for(int i=2; i<=n; i++) {
   		D[i] = D[i-1]+D[i-2];
   	}
   	
   	System.out.println(D[n]);
   }
   
   static int fibo(int n) {
   	// 기존에 계산한 적이 있는 부분의 문제일 경우
   	if (D[n] != -1) {
   		return D[n];
   	}
   	// 메모이제이션: 구한 값을 바로 리턴하지 않고
   	// DP 테이블에 저장한 후 리턴하도록 구현
   	return D[n] = fibo(n-2) + fibo(n-1);
   }

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런