본문 바로가기

Dev/coding

동적계획법

회사에서 심심할 때 보는 컴싸

동적계획법

 

알고리즘 설계 기법 알고리즘 패러다임(사고의 틀, 체계, 분류, 방법론):

동적계획법, 그리디, 백트래킹, 정렬

구현 알고리즘:

Djikstra, DFS, Breadth First Search, BFS, 최선 우선 탐색(Best First Search/Heuristic Search), Prim

Kruskal, Dijkstra, Juffman coding

n  동적계획법(DP)

답을 구하고 재활용하는 것, 재귀생각하면 됨

f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )

f(0,0) = 1, 임의의 자연수 n 대해 f(n,0) = f(0,n) = 1

이럴 때

 

그냥 계산시(재귀겠져) 5, 동적계획법쓰면 4

차이는 갈수록 커짐

(a,b)

그냥 계산시 연산 횟수

동적 계획법 이용시 연산 횟수

(2,2)

5

4

(4,4)

69

16

(6,8)

3002

48

(10,10)

184755

100

동적 계획법을 써서 구현할 있는 것들은 대개 백트래킹으로도 구현가능

동적 계획법이 빠르다. 하지만 대신 저장할 양이 많기 때문에 상황에 따라서는 동적 계획법으로는 메모리 오버플로우가 수도 있지만 백트래킹으로는 돌아가는 경우도 있다.

문제는 분할정복이나 재귀로 풀림, 하지만 시간 제한이 있다면? 동적계획법 만으로 풀린다.

'Dev > coding' 카테고리의 다른 글

그리디  (0) 2019.09.04
백트래킹  (0) 2019.09.04
동적계획법  (0) 2019.09.04
[python] python searching string within list  (0) 2019.08.24
[python] **dictionary  (0) 2019.08.24
[python] string format  (0) 2019.08.24