크래프톤정글 4주차; TIL 1 - DP, 피보나치 수 문제, 플로이드 알고리즘

2022-11-19, 2022-11-20

동적 프로그래밍 (dynamic programming)

참고: 에드위드 파이썬으로 배우는 알고리즘 기초 | 09. 동적 계획과 이항 계수
에드위드 [MIT] 파이썬을 이용한 알고리즘의 이해 | 동적 프로그래밍 1 : 메모이제이션, 피보나치 수, 최단 경로, 추측
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/mit6_006f11_lec19/
https://www.youtube.com/watch?v=-G8kDiMAPf8&list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl&index=22

무엇?

• 기본 개념
  • recursion + re-use(memoization)
  • 문제를 더 작은 문제로 분할하여 상향식으로 문제 해결
  • 알고자 하는 문제를 푸는데 도움이 되는 subproblem의 해를 구하고, 그것을 저장하고, 다시 불러와서 사용하는 것
  • 큰 문제의 해 = 작은 문제의 점화식
  • 더 작은 문제가 무엇인지 정의하는 것(defining subproblems)이 어려운 부분
  • controlled bruteforce (careful bruteforce) ⇒ 모든 추측을 “신중하게” 시도해보고 가장 좋은 것을 취하기
  • 일반적으로, 하위 문제를 위상 정렬하여 순서대로 해결 하는 것이 중요 (topological sort of subproblem dependency DAG) 상향식 접근법에서, for loop으로
    
    • 동적 프로그래밍과 메모이제이션이 작동하려면 비순환이어야 함
  • 동적 계획법을 이해하면 알고리즘의 5부 능선을 넘은 것
  • 이해도 어렵고 응용은 더 어렵다, 하지만 재밌습니다 <- 라고 교수님이 말하심…!!
• 리처드 벨먼이 발명
  • 벨먼-포드 알고리즘의 기초
  • 동적 계획법의 prgramming이란 '최적화optimization’의 뜻과 가까움 → 최대/최솟값 구하는 문제에서 많이 사용( ex. 최단 경로 구하기)
  • “basically it sounded cool …” (멋지게 들려서 그렇게 지었다고…)
• 용어
  • Programming : 동적 계획법의 programming은 '계획’을 의미함
  • Memoization : 가장 작은 입력 사례의 해답을 테이블에 저장하고 필요할 때 꺼내 쓰는 것(re-use하기)
  • DP 테이블: 작은 문제들의 해를 저장하는 테이블
• 분할정복법 vs 동적계획법 비교
  • 둘 다 문제를 작은 사례로 분할하여 해결함
  • 분할정복은 재귀 호출을 통한 반복 (탑다운)
  • 동적계획은 메모이제이션을 통해 상향식으로 정복 + 이미 저장한 답을 재사용함으로써 중복 계산을 피함 (바텀업) → 시간 면에서 더 좋다
• 시간복잡도
  • 하위 문제의 개수 * 하나의 하위 문제를 구하는데 걸리는 시간
  • 선형 시간

왜?

• 이번 주차 키워드 中 하나!
• 상당히 많은 문제들이 동적 계획법을 이용하여 쉽게 풀린다고 함
• 시간 복잡도가 일반 재귀 알고리즘보다 낮음! (하위 문제의 해를 기억해두기 때문)

어떻게?

• 동적 계획법으로 문제 풀기

1. 문제를 해결할 수 있는 재귀 관계식을 구한다
   • 이 때 보통, 마지막 답이 구해진 상태에서 한 단계 이전의 단계를 생각하면 실마리가 풀리는 경우가 많은 듯 함
2. 가장 작은 입력사례로부터 상향식 방법으로 문제를 해결

동적 프로그래밍; 피보나치 수 구하기

참고: 에드위드 [MIT] 파이썬을 이용한 알고리즘의 이해 | 동적 프로그래밍 1 : 메모이제이션, 피보나치 수, 최단 경로, 추측

무엇?

피보나치 수를 구하는 문제에서 subproblem은 F1, F2, … Fn을 구하는 것.

• 일반적인 재귀 알고리즘으로 해결하는 법
• DP 알고리즘으로 해결하는 법
  두 가지를 알아보고 비교하기

왜?

어떻게?

• naive recursive 알고리즘
  • f = f(n-1) + f(n-2) 를 이용함
  • 제곱의 시간 복잡도를 가짐 → 정확하지만 좋지 않은 알고리즘

fib(n):
	if n <= 2: 
		f = 1
	else: 
		f = fib(n-1) + fib(n-2)
	return f

• Dynamic Programming
  • 피보나치 수를 계산할 때마다 결과 값을 딕셔너리에 넣음
  • n번째 피보나치 수를 계산할 때마다 딕셔너리에 이미 그것이 있는지 확인함(이미 이 문제를 풀었는지 확인하는 것)
  • 풀었다면 답을 반환
  • 풀지 않았다면 값을 계산
  • ▽ 재귀 함수를 이용하는 방법(memoization)

  # 재귀 함수를 이용하는 방법(memoization)
  memo = {}
  def fib(n):
  	if n in memo:
  		return memo[n]
  	# 아래 네 줄의 if, else절은 일반 재귀 알고리즘의 그것과 동일함을 주목! 
  	if n <= 2: 
  		f = 1
  	else: 
  		f = fib(n-1) + fib(n-2)
  	memo[n] = f
  	return f
  

  • ▽ 반복문을 이용하는 법(상향식 접근)

    # 반복문을 이용하는 방법(상향식 접근)
    fib = {}
    for k in range(1, n+1):
    	if k <= 2:
    		f = 1
    	else:
    		f = fib[k-1] + fib[k-2]  # 이미 앞에서 계산한 것을 더하기
    	fib[k] = f
    print(fib[n])
    

    • 상향식 접근법에서는 공간을 절약할 수 있음
      • 꼭 필요한 마지막 두 개의 fib 수만 저장하고 나머지는 지워도 됨
    • 재귀 호출이 없어서 일반적으로 더 효율적

동적계획법; 최단 경로 문제 (플로이드 알고리즘)

참고: https://www.edwith.org/knu-algorithm/lecture/170189/?isDesc=false

무엇?

• 최단 경로 알고리즘 종류
  • 다익스트라
  • 플로이드
  • 벨먼
  • A* (A star)
• 주어진 그래프에서 모든 정점의 쌍에 대한 최단 경로를 구하기
• Directed Acyclic Weighted Graph
  • 싸이클이 있으면 빙글빙글 돌다가 경로가 늘어남

왜?

브루트포스로 최단 경로 문제를 해결할 시, 모든 정점간의 간선이 존재하는 경우 지수 시간 복잡도를 가짐(모든 경우의 수를 다 구함)

어떻게?

1. 재귀 관계식을 찾는다
   • D: 각 정점의 쌍이 갖는 최단 경로의 길이를 나타내는 행렬
   • D[i][j] : v_i에서 v_j로 가는 최단 경로의 길이
   • 목표: 인접 행렬 W에서 최단 경로의 행렬 D와의 재귀 관계식 구하기!
2. 상향식 방법으로 해답 구하기
   • 초기화: D⁰ = W
   • 최종 목표: Dⁿ = D
   • 상향식 계산: D⁰, D¹, D², …, Dⁿ
     • D⁰(= 입력으로 받은 W)로부터 D¹을 구하고, D¹으로부터 D²를 구하고, … D^n-1로부터 최종 해답인 Dⁿ(= D)을 구하는 것
   • 최단 경로 행렬의 이해
     • D^k : k개의 중간 노드를 거치는 최단 경로 길이의 행렬
       (ex. D¹[2][3] : 1개의 노드를 거쳐 2번 노드에서 3번 노드로 가는 최단 경로의 길이)
     • 따라서 D⁰는 아무 노드도 거치지 않고 가는 경로의 길이를 말하므로, W와 같음
     • Dⁿ은 다른 모든 정점을 지날 수 있는 최단 경로의 길이를 말하므로, D와 같음
   • 그러면 어떻게 D^k-1로부터 D^k를 구할 것인가?
     • D^k[i][j]는 다음과 같은 경우를 가짐
       1. 하나의 정점을 더 지나도 새로운 최단 경로가 없는 경우 ⇒ D^k[i][j] = D^k-1[i][j]
       2. 하나의 정점을 더 지나면 새로운 최단 경로가 있는 경우 ⇒ D^k[i][j] = D^k-1[i][k] + D^k-1[k][j]
          • principle of optimality: “i에서 k 까지의 최단 경로” + "k에서 j까지의 최단경로"가 "i에서 j까지의 최단 경로"를 보장함
          • 위의 법칙이 적용되어야 함
          • k는 하나가 아니라 여러 개일 수 있음
3. 최단 경로의 재귀 관계식
   • D^k[i][j] = min(D^k[i][j], D^k-1[i][k] + D^k-1[k][j])

INF = 999
W = # 그래프 V의 모든 간선을 나타내는 행렬 W

# 최단 경로 길이 구하기 
def floyd(W):
	D = W  
	n = len(W)
	P = [[-1] * n for _ in range(n)]
	for k in range(n):
		for i in range(n):
			for j in range(n):
				D[i][j] = min(D[i][j], D[i][k] + D[k][j])
	return D

D = floyd(W)
for i in range(len(D)):
	print(D[i])

# 최단 경로 구하기 
def floyd2(W):
	D = W  
	n = len(W)
	P = [[-1] * n for _ in range(n)]
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if (D[i][j] > D[i][k] + D[k][j]):
					D[i][j] = D[i][k] + D[k][j]
					P[i][j] = k
	return D, P

def path(P, u, v):
	if (P[u][v] != -1):
		path(P, u, P[u][v]) # u에서 k까지
		print("{P[u][v]} -> ")
		path(P, P[u][v], v) # k에서 v까지