[Algorithm] 동적계획법 Dynamic Programming, DP

🌟 동적계획법 Dynamic Programming, DP

정의:

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

• 문제를 단순화하고 점화식으로 만들어 재귀적인 구조를 활용해 해결하는 방식
  단순화 -> 점화식 -> 재귀적 구조 -> 해결
  

방법:

1. 전체 문제를 작은 문제로 단순화

2. 재귀적 구조를 활용할 수 있는 점화식 만들기

3. 작은 문제를 해결한 방법으로 전체 문제 해결

메모이제이션 Memoization:

정의:

동적계획법에서 사용하는 전략으로 함수의 값을 계산한 뒤 계산된 값을 배열에 저장하는 방식

특징:

필요할 때마다 호출하지 않고 값을 빠르게 가져올 수 있음

예시:

피보나치 수열

1. 재귀함수를 활용한 피보나치 함수

int fibo(int n){
	if(n < 2)
		return n;
    return fibo(n-1) + fibo(n-2);
}

2. 동적계획법을 활용한 피보나치 함수

int fibo(int n){
	if(n < 2)
    	return n;
    if(memo[n] != 0){
    	return memo[n];
    }
    else{
    	memo[n] = fibo(n-1) + fibo(n-2);
        return memo[n];
    }
}

재귀함수를 활용한 코드에서는
fibo(10)의 값이 구할 때 fibo(9) ~ fibo(1)까지의 값을 다 구해야 f(10)의 값을 구할 수 있다
f(n) = f(n-1) + f(n-2), f(n-1) = f(n-2) + f(n-3)...

하지만 동적계획법을 활용하면
fibo(10)의 값을 구할 때 fibo(9), fibo(8)의 값만 구하면 된다
f(n) = f(n-1) + f(n-2)

이전의 값들을 배열에 저장하기에 중복된 값이 나올 때는 재귀로 값을 다시 구하는 것이 아닌
구하고 저장했던 값을 가지고 와서 계산해줌
그렇기에 함수 호출 횟수가 줄어들고 효율적으로 실행

---

당신의 시간이 헛되지 않는 글이 되겠습니다.
I'll write something that won't waste your time.