Dynamic Programming이란?

1. Dynamic Programming(동적 계획법) 이란?

큰 문제를 작은 문제로 나누어 푸는 문제

 

 

 

1.1 Divide&Conquer(분할정복) 과 다른 점은?

거의 비슷하지만 결정적 차이가 있다.  작은 문제가 중복이 일어나나는 아닌지

 

분할 정복

• 큰 문제를 해결하기 어려워 단순히 작은 문제로 나누어 푸는 방법
• 작은 문제에서 반복이 일어나는 부분이 없다

DP

• 작은 부분 문제들이 반복되는 것(답이 바뀌지 않는다.)을 이용해 풀어나는 것

 

 

1.2 Dynamic Programming 방법

모든 작은 문제들은 한 번만 풀어야함.

정답을 구한 작은 문제들을 어딘가에 메모해놓고

다시 그보다 큰 문제 풀어나갈 때 똑같은 작은 문제가 나타나면

앞에서 메모한 작은 문제의 결과값 이용

 

 

1.3 Dynamic Programming의 조건

• 작은 문제가 반복이 일어나는 경우
• 같은 문제는 구할 때마다 정답이 같은 경우

이 조건 만족할 때만 DP 사용할 수 있다.

 

 

1.4 Memoization?

Memoization : 작은 문제들이 반복되고 이 작은 문제들의 결괏값이 항상 같으니 한번 계산한 작은 문제를 저장해 놓고 다시 사용하는 것

 

피보나치를 예로 들 수 있다.

 

재귀함수(Recursive)로 푼다면?

훨씬 간단하지만 n이 증가함에 따라 호출되는 함수의 수 기하급수적으로 증가해 일정 수 이상의 순열 구하기 어렵

 

 

def memoization_fibo(n):
	memo[0] = 1
    memo[1] = 1
    
    if (n < 2)
    	return memo[n]
        
    for i in range(2, n+1):
    	memo[i] = memo[i-2]+ memo[i-1]
	return memo[n]


if __name__ == '__main__':
	n = int(sys.stdin.readline())
    memo = [0 for i in range(n+2)]
    print(memoization_fibo(n))

 

 

1.5 장점 단점

DP는 모든 방법 일일이 검토해 최적의 해를 찾아내는 방식의 알고리즘으로 그리디 알고리즘과 대비된다.

 

그리디 알고리즘은 모든 해 구하지 않고 그 순간에서의 최적의 해 찾는 방식

닥치는 순간만을 고려해 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 순 없다.

 

DP는 모든 방법을 검토해 보고 결과적으로 효율적인 값 택

DP가 그리디 보다 시간이 오래 걸리지만 결과적으론 항상 최적의 해를 구할 수 있다는 장점있다.

 

 

 

 

 

2. Bottom-up 과 Top-down

 

2.1 구현 방법

 

1.Bottom-up

작은 문제부터 차근 차근 구해나가기

 

2. Top-down

재귀함수로 구현하는 경우가 대부분 top-down

큰 문제를 풀 때 작은 문제가 풀리지 않았다면 그때 작은 문제를 해결

 

 

둘 중 뭐가 좋을지는 정답 없음

bottom-up 풀기 쉽지만 가독성 저하

top-down은 소스 가독성 증가 but 작성 어렵

 

 

 

 

팁?

큰 문제가 있을 때 그것의 가장 작은 문제부터 생각해보자

작은 문제 해결해서 규칙 찾고 작은 문제들 답 가지고 점화식 도출해보자

 

 

 

참고 사이트

galid1.tistory.com/507

velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP