README.md

동적 계획법

동적 계획법이란?

하나의 큰 문제를 여러 개의 작은 문제로 나누어 푸는 방법

나누어진 작은 문제들의 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것

DP를 쓰는 이유

피보나치 수열

대표적인 재귀 함수 예시

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

• 피보나치 수열의 n 번째 수를 구하는 함수 (재귀)

def fibo(n):
    if n <= 2:
        return 1
    else:
        return fibo(n - 1) + fibo(n - 2)

시간 복잡도 : O(2^n)

fibo(6)을 실행하면 동일한 연산이 여러번 진행된다.

동적계획법 (DP)

처음 진행되었던 연산을 기록해두고, 이를 다시 재활용하는 방식이다.

• 피보나치 수열의 n 번째 수를 구하는 함수 (DP)

def fibo(n):
    dp = [0] * (n+1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n+1):
        dp[i] = dp[i-2] + dp[i-1]
    return dp[n]

시간복잡도 : O(n)

dp라는 배열에 연산한 값들을 저장한다.

dp[i] = dp[i-2] + dp[i-1] (점화식)을 활용하여 이전에 계산한 값들을 사용하여 더 큰 값을 계산한다.

→ 중복된 연산 X

DP 사용 조건

• 동일한 작은 문제들이 반복하여 나타나는 경우
• 같은 문제는 항상 정답이 같은 경우

즉, ‘계속 반복되는 연산’을 활용하여 ‘메모제네이션’으로 빠르게 푸는 것이 핵심이다.

메모제네이션 : 한 번 계산한 문제는 다시 계산하지 않도록 저장해두고 활용하는 방식

구현 방식

- Bottom-Up 방식

: 아래에서부터 계산을 수행해서 전체 큰 문제를 해결하는 방식

피보나치에서의 DP 방식으로 보였던 예시이다.

점화식을 사용해서 이전 값들을 사용해 더 큰 값을 계산하는 방식이다.

- Top-Down 방식

: 위에서부터 바로 호출을 시작하는 방식

• Top-Down 방식으로 피보나치의 n 번째 수를 구하는 함수

dp = [0] * (n+1)
dp[0], dp[1] = 0, 1

def fibo(n):
		if n<=2:
				return 1
		if dp[n] == 0:
        dp[i] = fibo[i-2] + fibo[i-1]
    return dp[n]

dp[n] 의 값을 찾기 위해 dp[0] 까지 내려간 다음 결과 값을 재귀를 통해 재활용하는 방식

분할정복과 동적계획법

주어진 문제를 작게 쪼개서 큰 문제를 해결하는 점이 동일하다.

차이점은

• 분할 정복: 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우
• 동적계획법: 분할된 하위 문제에서 동일한 중복이 일어나는 경우

---

• 출처
• 출처