[알고리즘] DP

취업 준비를 시작하며 알고리즘을 배울 때

아, 이건 DFS 문제구나. 라고 생각해서 DFS로 푼 문제가 있었다.

하지만 정확도는 100%여도 효율성은 0에 가까운 결과를 보여주었었는데,

같은 알고리즘을 풀던 친구에게 물어보니 해당 알고리즘은 DFS가 아니라 DP로 풀어야 한다고 대답을 해줬었던 기억이 있다.

 

 

 

DP (동적 계획법, Dynamic Programming)

 

알고리즘을 풀다보면 연산이 쓸데없이 반복되는 경우가 있다.

피보나치 수열이 그 예시이다.

피보나치 수열

첫째, 둘째 항이 1이며 그 뒤의 모든 항들은 앞의 두 항의 합인 수열.

 

평범한 피보나치 수열 구하기 문제의 코드는 다음과 같다.

public class main{
	public static void main(String[] args) {
		int result = fibo(10);
		
		System.out.println(result);
	}
	
	public static int fibo(int n) {
		if(n <= 2) return 1;
		else return fibo(n-1) + fibo(n-2);
	}
}

그렇다면 100번째 항을 구하기 위해 각 항들은 몇 번이나 계산이 될까?

 

각 n번째 항들이 계산에 사용되는 횟수를 저장하여 확인해보자.

public class main{
	private final static int n = 11;
	private static int[] count = new int[n];
	public static void main(String[] args) {
		int result = fibo(n-1);
		
		System.out.println(result);
		for(int i=1; i<n; i++) {
			System.out.println(i + " : " + count[i]);
		}
	}
	
	public static int fibo(int n) {
		count[n]++;
		if(n <= 2) return 1;
		else return fibo(n-1) + fibo(n-2);
	}
}

보다시피 한 번씩만 하면 되는 계산이 쓸 데 없이 많이 진행되었었음을 확인할 수 있다.

DP는 이러한 반복되는 연산의 결점을 보완하기 위한 알고리즘이다.

 

앞선 코드는 이전에 실행했던 연산의 결과를 보관하지 않는다는 단점으로 인해 쓸데없는 반복 연산이 발생했다. 이를 보완하기 위해 DP는 이전에 실행했던 연산을 기록하고, 다시 가져와 쓸 데 없는 반복 연산을 없앴다.

 

다음은 DP를 활용한 피보나치 수열 구하기 알고리즘이다.

public class main{
	private final static int n = 11;
	private static int[] count = new int[n];
	public static void main(String[] args) {
		int[] fiboArray = new int[n];
		int result = fibo(n-1, fiboArray);

		System.out.println(result);
		for(int i=1; i<n; i++) {
			System.out.println(i + " : " + count[i]);
		}
	}
	
	public static int fibo(int n, int[] fiboArray) {
		count[n]++;
		if(n <= 2) return 1;
		
		if(fiboArray[n] == 0) {
			fiboArray[n] = fibo(n-1, fiboArray) + fibo(n-2, fiboArray);
		}
		
		return fiboArray[n];
	}
}

결과값을 확인해보면 연산량이 확연하게 줄었음을 확인할 수 있다.

 

 

예시

프로그래머스 알고리즘 중 DP를 사용한 예시이다.

https://123okk2.tistory.com/42

[JAVA][DP] 정수 삼각형_programmers level 3