다익스트라, 동적계획법

다익스트라 알고리즘

설명

최단 경로 계산에 실제로 계산되는 알고리즘으로 다음과 같은 과정으로 진행된다.

• 출발지 s를 정하고 거리를 0으로 작성한다.
• s에서 갈 수 있는 노드들의 거리를 측정하여 작성한다. ( t: 10, y: 5 )
• 방문 안한 노드들 중 가장 가까운 노드 y를 방문하고 최소 거리를 작성한다. (y는 5로 확정!)
  • y를 갈 수 있는 방법은 t를 거쳐서 가는 것보다 당연히 y로 가는 게 가장 최단 거리이다.
• 모든 노드를 방문할 때까지 반복한다.

구현

import heapq

def dijstra(graph, start):
    # 모든 노드의 최소 비용을 무한대로 설정
    INF = 1e9
    result = [INF] * len(graph)
    # 출발점의 최소 비용을 0으로 설정
    result[start] = 0
    # 힙에 출발점의 누적 비용과 노드 번호을 저장(heapq는 0번째 인덱스로 최소힙을 돌림)
    q = []
    heapq.heappush(q,(0,1))
    # 모든 노드에 방문할 때까지 반복
    while q:
        distance, node = heapq.heappop(q)
        # q에 누적 비용을 넣어놓고 q가 도는 사이 최소 비용을 찾은 경우
        # old 누적 비용은 고려할 필요가 없음(예: x 노드는 q에 13이 들어가지만 그 다음에 9로 최소 비용을 찾으므로 13에 대해서는 pass)
        if distance > result[node]:
            continue
        # 그게 아니라면 최소 비용을 찾은 것이므로 갱신
        result[node] = distance
        # 인접 노드들 확인
        for nextNode, cost in graph[node]:
            new_cost = distance + cost
            # new_cost가 result의 누적비용보다 더 최소라면 heapq에 추가
            if new_cost < result[nextNode]:
                result[nextNode] = new_cost
                heapq.heappush(q, (new_cost, nextNode))
    return result

 

동적 계획법

설명

동적 계획법(DP)란, 여러 개의 하위 문제를 풀고 그 결과를 기록해 이용하는 알고리즘이다. 재귀함수를 사용할 때 했던 함수의 수식화를 하면 된다. 단, 그 결과를 기록하고 이용한다는 점이 동적 계획법의 특징이다.

문제 1 (피보나치 수열)

피보나치 수열을 일반적으로 구현하면 다음과 같다.

def fibo(n):
    if n in [1, 2]:
        return 1
    return fibo(n-1) + fibo(n-2)

하지만 실제로 돌려보면 아래와 같은 로직으로 너무 많은 시간이 걸리게 된다.

f(4)는 두 번, f(3)은 세 번 계산된다.

DP를 사용하면 아래와 같이 구현하여 이미 계산한 값은 두 번 계산하지 않는다.

memo = {1: 1, 2: 1}

def fibo_dp(n):
    if n in memo:
        return memo[n]
    memo[n] = fibo_dp(n - 1) + fibo_dp(n - 2)
    return memo[n]

문제 2 (극장 좌석 자리 구하기)

극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

총 좌석의 개수와 VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 반환하는 문제이다.

 

처음 보면 어떻게 풀어야할 지 감이 잘 오지 않기 때문에, 간단한 예제부터 하나씩 생각해보자.

N=1 일 때, 1이다. N=2 일 때, 2이다.
N=3 일 때에는? 쪼개서 생각해보자. 3은 자기 자리에 앉거나, 다른 자리에 앉거나로 나눌 수 있다. 그러면, N=3일 때에는 (N=2일 때 가짓수) + (N=1일 때 가짓수)이다. 

즉, DP(N) = DP(N-1) + DP(N-2)이다!

 

VIP인 경우를 고려하면 어떻게 될까? 고정된 VIP 자리를 앞 뒤로 경우의 수를 곱해주면 된다.

thea_memo = {
    1: 1,
    2: 2,
}

def dp(n):
    if n in thea_memo: return thea_memo[n]
    thea_memo[n] = dp(n-1) + dp(n-2)
    return thea_memo[n]

def theater_seat(n, vips):
    answer = 1
    before_vip = 0
    for vip in vips:
        cnt = dp(vip - 1 - before_vip)
        answer *= cnt
        before_vip = vip
    answer *= dp(n - before_vip)

    return answer

최장 증가 부분 수열(LIS)

문제

설명

동적 계획법을 사용하기 위해 함수화를 해보자. f(n) = n번째 숫자를 포함한 최장 길이라고 하면, f(n)은 f(n보다 작은 수 중 가장 큰수) + 1 또는 1이 된다.

구현

# 최장 증가 부분 수열(LIS)
nums = list(map(int,input().split(" ")))
result = [ 1 for _ in range(len(nums))]

for i in range(1,len(nums)): 
    for j in range(0,i):
        if nums[j] < nums[i] and (result[j] + 1) > result[i]:
            result[i] = result[j] + 1

result.sort
print(result[-1])