[이것이 코딩테스트다] 7. 다이나믹 프로그래밍

이것이 취업을 위한 코딩테스트다.

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

 

 

다이나믹 프로그래밍(Dynamic Programming)

1. 피보나치 수열을 재귀함수로 구현

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int result = fibonacci(4);
		
		System.out.println(result);
	}
	
	static int fibonacci(int num){
		if(num == 1 || num == 2) {
			return 1;
		}
		return fibonacci(num-1) + fibonacci(num-2);
	}

}

위처럼 재귀함수로 구현한 경우, 30번째 수를 구하려고 한다면 약 10억 가량의 연산을 수행해야한다.

 

하지만, 기존에 계산한 결과를 추후에 다시 계산하지 않도록 따로 저장해둔다면 어떨까?

 

이 방법을 '메모이제이션(Memoization) 기법' 이라고 한다.

 

 

2. 피보나치 수열을 메모이제이션 기법으로 구현

public class Main {

	// 계산된 값들을 저장
	static long[] arr = new long[100];
	
	public static void main(String[] args) {

		System.out.println(fibonacci(50));
	}
	
	static long fibonacci(int num){
		if(num == 1 || num == 2) {
			return 1;
		}
		
		// 해당 피보나치 수열에 대한 계산 값이 없으면 계산
		if(arr[num] == 0) {
			long result =  fibonacci(num-1) + fibonacci(num-2);
			arr[num] = result;
			
			return result;
		}
		// 계산 값이 있으면 그 값을 가져와서 반환
		else {
			return arr[num];
		}
	}

}

위의 코드는 메모이제이션 기법을 이용한 소스이다

 

arr 배열에 피보나치 수열들의 계산 결과를 넣어두면 추후에 다시 계산하지 않아도 되어 효율적이다.

 

이처럼, 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 '탑다운(Top-Down) 방식' 이라고 한다.

 

그렇다면, 작은 문제부터 답을 도출하는 보텀업 방식을 알아보자.

 

3. 피보나치 수열을 반복문으로 구현

public class Main {

	// 계산된 값들을 저장
	static long[] arr = new long[100];
	
	public static void main(String[] args) {

		int N = 50;
		
		arr[1]=1;
		arr[2]=1;
		
		// 50까지의 모든 계산 결과 저장
		for(int i=3;i<=N;i++) {
			arr[i] = arr[i-1] + arr[i-2];
		}
		
		System.out.println(arr[N]);
	}
	
}

위 소스는 반복문을 이용하여 작은 문제부터 계산을 진행하는 보텀업 방식이다.

 

시스템 상, 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문에 재귀함수를 이용하는 탑다운 방식보다는 반복문을 이용한 보텀업 방식으로 구현하는 것을 권장한다.