[알고리즘] 6. 동적 계획법

KOCW에서 제공하는 고려대학교 유용재 교수 알고리즘 강의를 듣고 정리한 글 입니다.

6주차 동적 계획을 이용한 문제 해결 성능 제고

---

 

6주차. 동적 계획을 이용한 문제 해결 성능 제고

 

 

1. 동적 계획의 이해와 구현

1) 동적 계획법이란?

• 복잡한 문제를 보다 단순한 여러 문제로 쪼개어 해결하는 패러다임
• 과거에 계산하였던 결과를 활용한다는 점에서 분할 정복법과 차이가 있음
• 점화식을 세워 문제를 해결하는 형태로 동적 계획을 활용하는 경우가 다수
• 점화식 : 앞의 항과 뒤의 항의 관계를 나타낸 식

 

2) 동적 계획법을 효과적으로 구현하는 방식

(1) Memoization

• 최상위 문제에서 시작하는 Top-down 접근법
• 중간 과정에서의 값을 기록하여 효율성 제고
• 예) 피보나치 수열을 DP로 계산한 경우 f(10) = f(9)+f(8), f(9) 계산 시 f(8) 계산 결과를 저장해놓는 방법. 기록안해놓으면 "+ f(8)" 계산 시, 다시 계산하게됨
•  

# Week 6

# Dynamic Programming
# Fibonacci, DP

def fibo(N):
  if (N == 0) or (N == 1):
    return 1
  return fibo(N-1) + fibo(N-2)
  
print(fibo(100))

# result
# Error: Command failed: timeout 7 python3 main.py

# Week 6

# Dynamic Programming, Memoization
# Fibonacci (DP + Memoization)

def fibo(N):
  if (fibo_list[N] != -1):
    return fibo_list[N]
    
  else:
    fibo_list[N] = fibo(N-1) + fibo(N-2)
    return fibo_list[N]
  
fibo_list = [1, 1]

for i in range(1, 10000):
  fibo_list.append(-1)
  
print(fibo(100))

# result
# 573147844013817084101

(2) Tabulation

• 최하위에서 시작하는 Bottom-up 방식
• 빈 표에값을 쌓아가는 방식

 

# Week 6

# Dynamic Programming, Tabulation
# Fibonacci (DP + Tabulation)

def fibo(N):
  fibo_list = [1, 1]
  
  for i in range(1, 10000):
    fibo_list.append(-1)
  
  for i in range(2, N+1):
    fibo_list[i] = fibo_list[i-1] + fibo_list[i-2]
  return fibo_list[N]
  
print(fibo(100))

 

2. 동적 계획을 이용한 문제 해결

1) 동적계획을 잉요한 문제해결의 핵심은 점화식 찾기

 

3.  복잡한 상황에서의 동적 계획

1) 문제 예시

(1)  2xn 타일링

 

(2) 고연전/연고전 기차놀이

 

 

 

4. 자료구조와 동적 계획법

1) Floyd-Warshall Algorithm

출발지 A에서 B까지 갈 수 있는 방법 1) 바로 간다 2) 경유지 C를 거쳐간다 

경유지를 거칠 경유, A->C + C->B 가 새로운 최단 시간 후보. 이를 반복

 

# Week 6

# DP
# Floyd-Warshall Algorithm

def flydwarshall(graph, graph_v, start):
	# 불가능한 이동 inf 처리
    for i in range(0, len(graph)):
    	for j in range(0, len(graph)):
        	if (i != j) and (graph[i][j] == 0):
            	graph[i][j] = float('inf')
	
    # 모든 시작-끝에 경유 계산, 비교
	for mid in range(0, len(graph)):
		for start in range(0, len(graph)):
			for end in range(0, len(graph)):
				new_weight = graph[start][mid] + graph[mid][end]
                graph[start][end] = min(graph[start][end], new_weight)
 	
    # print
	for i in range(0, len(graph)):
    	for j in range(0, len(graph)):
      		print(graph_v[i], '->', graph_v[j], '최단 거리 : ', graph[i][j])

G = [[0, 30, 0, 20, 0],
        [40, 0, 0, -30, 0],
        [0, 50, 0, 0, 30],
        [0, 0, 0, 0, 60],
        [0, -20, 0, 0, 0]]

V = ['A', 'C', 'E', 'B', 'D']

flydwarshall(G, V, 0)

# result
'''
A -> A 최단 거리 :  0
A -> C 최단 거리 :  30
A -> E 최단 거리 :  inf
A -> B 최단 거리 :  0
A -> D 최단 거리 :  60
C -> A 최단 거리 :  40
C -> C 최단 거리 :  0
C -> E 최단 거리 :  inf
C -> B 최단 거리 :  -30
C -> D 최단 거리 :  30
E -> A 최단 거리 :  50
E -> C 최단 거리 :  10
E -> E 최단 거리 :  0
E -> B 최단 거리 :  -20
E -> D 최단 거리 :  30
B -> A 최단 거리 :  80
B -> C 최단 거리 :  40
B -> E 최단 거리 :  inf
B -> B 최단 거리 :  0
B -> D 최단 거리 :  60
D -> A 최단 거리 :  20
D -> C 최단 거리 :  -20
D -> E 최단 거리 :  inf
D -> B 최단 거리 :  -50
D -> D 최단 거리 :  0
'''