[자료구조] 동적계획법 알고리즘 ( Dynamic Algorithm)

동적계획법 알고리즘은 하나의 문제를 반복해서 풀지 않고 한번만 풀도록 해주는 알고리즘이다.

 

동일한 문제를 풀게되는 방식의 가장 대표적인것이 분할정복 기법이 있다.

 

분할 정복 기법은 하나의 문제를 잘게 쪼개서 작은 문제를 해결이 완료되고 나면 return을 하여서 

작은 문제들의 결과를 하나로 취합해 큰 문제를 해결해 나가는 방식이다. 

 

퀵정렬과 같은 알고리즘에는 분할 정복 기법이 잘 적용되서 빠르게 문제를 해결해 나갈수 있지만

 

피보나치 수열을 구하는 문제에서 분할정복 기법이 적용되면 시간복잡도는 엄청나게 커진다.

 

피보나치 수열은 

 

1, 1, 2, 3, 5, 8, 13...

 

이처럼 수를 구하는것이다.

그래서 맨 처음 index인 1과 2까지 재귀호출을 하면서 내려가게된다.

 

그런 상황에서 분할정복 기법을 사용하면 아래와 같아진다.

위 그림처럼 분할정복 기법으로 피보나치수를 구하게 된다면 이미 했던 계산을 또하게 되고

노드가 밑으로 점점 계속해서 내려가서 노드의 개수만큼 내려간다.

그리고 내려갈때마다 노드의 수는 2개씩 늘어나서 분할정복기법으로 피보나치 수열의 문제를 풀게 되면

시간 복잡도는 O(2^n)이 된다.

 

피보나치 수열을 소스를 구현하면아래와 같다.

 

main 함수

	public static void main(String[] args) {
		// TODO Auto-generated method stub

//		PreTest p = new PreTest();
		
		Dynamic dp = new Dynamic();
		int n = 10;
		System.out.println(dp.pivo(50));

	}

Dynamic 클래스

public class Dynamic {
	
	public int pivo(int n) {
		if(n == 1)
			return 1;
		if(n == 2)
			return 1;
		return pivo(n-1) + pivo(n-2);
	}
	
}

위 소스처럼 50이란 수를 하게 되면수는 엄청 커져서 오랜시간이 걸리게 된다.

 

그래서 피보나치 수열과 같은 문제는 동적계획법 알고리즘에 따라서 문제를 풀어야 한다.

 

동적 계획법 알고리즘은 이미했던 문제의 값을 특정배열에 저장후 

해당 배열을 확인해 이미 풀었던 문제라면 해당 배열의 값을 가져와서 다시 계산하는 일을 없게 만드는 것이다.

 

그래서 그림으로 표현하자면 아래와 같아진다.

이미 8과 7은 아래에서 해결을 했기때문에 따로 또 계산을 하지 않는것이다.

 

그럼 이제 소스를 통해서 어떻게 되는지 확인을 해보자.

 

main 함수

	public static void main(String[] args) {
		// TODO Auto-generated method stub

//		PreTest p = new PreTest();
		
		Dynamic dp = new Dynamic();
		int n = 50;
		
		int[] arr = new int[n];
		
		System.out.println(dp.pivo(n,arr));

	}

Dynamic 클래스

public class Dynamic {
	
	public int pivo(int n, int[] arr) {
		if(n == 1)
			return 1;
		if(n == 2)
			return 1;
		if(arr[n-1] != 0) {
			return arr[n-1];
		}
		return arr[n-1] = pivo(n-1,arr) + pivo(n-2,arr);
	}
	
}

 

 

이렇게 배열을 이용해서 계산한 값을 해당 index에 넣고 관리를 하게 되면 불필요한 계산을 또 할 필요가 없어져서

시간복잡도는 노드 개수만큼 하게 되면 O(n)이 된다.