[알고리즘] 동적 계획법 (Dynamic Programming)

동적계획법 (Dynamic Programming)

• 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식
• 그리디나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미한다.
• Dynamic Programming(DP)라고도 부른다.
• 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다.
• 두 가지 방법론이 있다.
  • 메모이제이션(Memoization)
  • 타뷸레이션(Tabulation)

메모이제이션 (Memoization)

• 하향식 접근법
• 동적 계획법에서 작은 문제들의 결과는 항상 같다.
• 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다.

메모이제이션의 단점은 재귀를 이용하기 때문에 스택이 너무 많이 쌓이면 과부화에 걸릴 수 있다는 점이 있다.

타뷸레이션 (Tabulation)

• 상향식 접근법
• 필요한 값들을 미리 계산해두는 것
• 메모이제이션은 필요할 때 계산한다면 타뷸레이션은 미리 계산해둔다.
• 보통 코딩 테스트에선 메모이제이션을 쓰는 경우가 대부분이다.

타뷸레이션의 단점은 표를 하나씩 밑에서부터 채워야 하기 때문에 불필요한 값을 계산해야 할 수도 있다.

동적 계획법 문제 유형 확인 방법?

• '가장 작은 문제를 정의할 수 있는지?' 확인
• 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는지?
• 위 두 가지가 가능하다면 동적 계획법 문제이다.

피보나치 수열

피보나치는 1,1,2,3,5,8 ...의 수를 이루게 된다.
즉, 다음 수열 = 이전 수열 + 두 단계 전 수열의 합 으로 계산되는 점화식을 갖는 순열이다. 재귀 함수로 풀게 되면 임의의 n이 증가함에 따라 중복으로 호출되어 계산되는 함수의 수가 증가하기 때문에 일정 수 이상의 순열을 구하기 어렵고, 효율성이 좋지 않다.

이때, 동적 계획법을 이용해 풀 수 있다.
위에서 언급한 동적 계획법 문제 유형 확인 방법을 돌이켜보면,

1. 작은 문제를 정의할 수 있는가? => Yes

• 피보치나 값을 쪼개서 따로 계산하여 메모이제이션 할 수 있다.

2. 작은 문제를 통해 큰 문제를 해결할 수 있는가? => Yes

• 메모이제이션 된 값들을 중복 계산을 줄이고, 구하고자 하는 n의 값을 구할 수 있다.

// 동적 계획법을 이용한 코드
function fibo(n) { 
	let dp = Array.from({length:n+1},()=>0};
  	dp[0] = 0;
  	dp[1] = 1;
  	for(let i=2;i<=n;i++) {
    	dy[i] = dy[i-1] + dy[i-2];
  	}
  	return dy[n];
}

장점

동적 계획법(DP)는 모든 방법을 확인하여 최적의 해를 찾아내는 알고리즘 입니다. 동적 계획법은 메모리를 많이 사용하는 대신 빠르게 모든 방법을 확인하여 최적의 해를 구할 수 있다는 장점이 있습니다.