[Algorithm] 동적 계획 알고리즘

동적 계획 알고리즘에 대해 공부하기 전에,,

이전에 포스팅했던 분할정복 방법! 다시 살펴보기

 

💡분할정복 방법?

• 하향식 top-down 접근법
• 상위 레벨의 복잡한 문제를 재귀적으로 작은 문제들로 나누고, 이들의 해를 결합해서 문제를 해결하는 방법
• 분할된 부분 문제들은 서로 독립적
• 퀵정렬, 합병 정렬, 이진 탐색

➰피보나치 수열을 분할 정복으로?

• 같은 계산이 반복됨 -> 비효율적!

 

---

💡동적 계획 알고리즘?

• 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘 
• 작은 문제에 대한 결과를 테이블에 저장해 놓고, 이를 이용하여 입력의 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 방법
• 최댓값/최솟값을 구하는 최적화 문제에 적용
• 부분 문제들 사이에 의존적 관계가 존재한다. 
  • 이러한 관계는 문제 또는 입력에 따라 다르고, 대부분의 경우 뚜렷이 보이지 않아서 '함축적인 순서 (implicit order)'

 

1. 먼저 입력크기가 작은 부분 문제들을 모두 해결한 후에
2. 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여,
3. 최종적으로 원래 주어진 입력의 문제를 해결

 

➰피보나치 수열을 동적 프로그래밍 으로? (O(n))

int fib_DP(n) {
	int i, f[n];
    f[0] = 0;
    f[1] = 1;
    for(i=2;i<=n;i++)
    	f[i] = f[i-1] + f[i-2];
    return f[n];

• 상향식 botton-up 접근법
• 작은 문제는 서로 독립적이지 않고, 중복 부분이 존재한다. -> 상위레벨에서 부분문제의 해를 중복 사용할 수 있다.

 

최적성의 원리

• 주어진 문제에 대한 최적해가 분할된 부분문제의 최적해로 구성된다는 원칙

1. 욕심쟁이 방법
   • 각 단계의 국부적인 최적해가 전체적인 최적해를 구성
   • 각 단계에서 하나의 최적해만 고려
   • -> 전체적인 최적해를 구하지 못할 수도 있다.
2. 동적 프로그래밍 방법
   • 작은 문제에 대한 모든 가능성을 고려해서 다음 크기의 문제에 대한 최적해를 결정
   • -> 항상 최적의 결과를 얻을 수 있다.

 

💡동적 프로그래밍의 적용단계

1. 문제의 특성을 분석하여 최적성의 원리가 성립되는지를 확인
2. 주어진 문제에 대해서 최적해를 제공하는 점화 관계식을 도출
3. 가장 작은 부분문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장
4. 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 입력크기가 큰 상위 문제의 해를 구함

 

---

응용문제

1. 모든쌍 최단 경로 : O(n^3)
2. 연속된 행렬 곱셈 : Θ(n^3)

 

---

Reference

서울과학기술대학교 컴퓨터공학과 알고리즘 수업

알기쉬운 알고리즘 도서