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

알고리즘 문제를 풀다 보면 동적계획법에 관련된 문제들을 많이 볼 수 있다.

옛날에 알고리즘 스터디할 때 하긴 했는데 제대로 이론을 안하고 문제만 풀어서 그런지

오랜만에 코딩을 하니까 기억이 안나서 다시 공부하고 정리를 하려 한다.

 

---

다이내믹 프로그래밍, 동적계획법 (Dynamic Programming, DP)

하나의 문제는 한 번만 풀도록 하는 알고리즘, 한번 푼 것을 여러 번 다시 풀지 않는 효율적인 알고리즘

크고 어려운 문제가 있을 때 큰 문제를 잘게 나누어 해결한 뒤에 전체의 답을 구하는 방법

최적화 문제를 해결하는 데 유용함

 

최적화 문제 : 문제의 답이 여러 개 존재하며 가장 좋은 결과를 찾아야 하는 문제 (ex. 최단경로 문제)

 

다이내믹 프로그래밍을 사용하는 이유

분할-정복 기법(divide-conquer)은 특정 문제에 대해서는 동일한 문제를 다시 푼다는 치명적인 단점이 있다.

불필요한 계산을 여러 번 해야 하므로 굉장히 비효율적이다.

이런 경우에는 계산 횟수, 시간 복잡도 등을 감소시키기 위해서 다이내믹 프로그래밍 기법을 사용해야 한다.

 

<단순 재귀로 피보나치 수를 구하는 코드>

int f(int x) {
	if(x==1) return 1;
	if(x==2) return 1;
	return f(x-1)+f(x-2);
}

 

<다이내믹 프로그래밍으로 피보나치 수를 구하는 코드>

int dp(int x){
	if(x==1) return 1;
	if(x==2) return 1;
 	if(d[x] != 0) return d[x];
	d[x] = dp(x-1) + dp(x-2);
	return d[x];
}

 

다이내믹 프로그래밍을 사용하는 경우

1) 큰 문제를 작은 문제로 나눌 수 있는 경우

2) 작은 문제에서 구한 정답이 그 문제를 포함하는 큰 문제에서도 동일한 경우 -> 작은 문제들이 서로 종속성을 가짐

 

위의 1)과 2)를 동시에 만족시키는 경우에는 다이내믹 프로그래밍을 사용할 수 있다.

 

 

메모이제이션(Memoization)

이미 계산한 결과를 배열에 저장함으로써 나중에 동일한 연산을 해야 할 경우 배열에 저장된 값을 반환한다.

---

참고 강의 :

https://youtu.be/FmXZG7D8nS4