ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[DP] Ch08-다이나믹 프로그래밍

Posted on Feb 19, 2021 #동적프로그래밍(DP)  

중복되는 연산을 줄이자

다른 단원과는 달리 동적 프로그래밍의 개념이 잘 기억나지 않아 책의 내용을 따로정리한다.
동적 프로그래밍 == 다이나믹 프로그래밍 == DP 이며, 이 블로그에서는 모두 혼용해서 사용하고 있다.

🚩 다이나믹 프로그래밍을 사용할 수 있을 조건

  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

다이나믹 프로그램은 재귀함수 등으로 문제를 풀때보다 효율적이다(ex. 피보나치 수열). 또한 동적 할당의 다이나믹과는 다른 의미이다. (‘프로그램 실행중에’ 라는 뜻을 가지고 있다.)

다이나믹 프로그래밍에는 2 가지 방식이 있는데, 바로 Top-down(하향식)과 Bottom-up(상향식)이다. 또한 자주 사용하는 메모이제이션(캐싱)기법도 있다.

  • 캐싱이란 한 번 푼 문제는 결과를 리스트에 저장해 놓았다가 나중에 동일한 문제를 풀때 이미 저장한 값을 반환하는 것을 말한다. 이는 Top-down, 즉 하향식 방법에 국한된 문제풀이 방식이다.

캐싱을 사용해서 피보나치 수열을 구현해보자

vector<long long> v(100); // int 형 vector를 크기 100으로 할당후 모든 원소 0으로 초기화
long long fibo(int x) {
	if (x == 1 || x == 2) {
		return 1;
	}
	if (v[x] != 0) {
		// 이미 계산된 경우라면 값 바로 반환
		return v[x];
	}
	v[x] = fibo(x - 1) + fibo(x - 2);
	return v[x];
}

위의 경우 시간 복잡도는 O(n)이다. * 재귀함수를 이용한 피보나치 수를 구할 경우 O(2n).

동적 프로그래밍의 전형적인 형태는 Bottom-up(상향식)방법이다. 이 방식에서 사용되는 결과 저장용 리스트를 DP table이라고 부른다.

특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 동적 프로그래밍을 적용할 수 있는지 부분문제의 중복 여부를 확인한다.

먼저 작성한 재귀함수를 캐싱을 통해 탑다운으로 코드를 수정하는 것도 좋은 방법이지만, 가능하다면 탑다운 방식보단 보텀업 방식으로 구현하는 것이 권장된다. 시스템상 스택 크기가 한정되어 있을 수 있기 때문이다.

위의 피보나치 수열 문제를 상향식으로 풀어본다면?

피보나치 수열문제를 상향식으로 풀이한 코드는 백준 2747번에 이미 포스팅했으므로 링크를 첨부한다.



# 카테고리