정글사관학교 23일차 TIL: 플로이드 와샬, 동전 2(#2294)

0. 목차

1. 플로이드 와샬 개념 정리

2. 구슬 찾기 문제 풀이

3. 동전 2 풀이 (with DP)

 

1. 플로이드 와샬 개념 정리

개념 정리 출처: 나동빈 유튜브

 

플로이드 와샬 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다. 다익스트라와 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만 다익스트라가 출발점을 고정했을 때의 최단 경로만을 계산한다면 플로이드 와샬은 전체 통으로 스캔하는 개념이라고 생각하면 될듯. 하지만 여기서 무식하게 싹다 스캔하는 게 아니라 일종의 DP를 이용해 최단거리 노드를 기록한다.

 

시간복잡도

플로이드 와샬의 시간 복잡도는 O(n**3)이다.

 

점화식

Dab = min(Dab, Dak + Dkb)이며, 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. 이런 점에서는 다익스트라와 유사한 개념이라 할 수 있다. 이때, a에서 b로 가는 최단 거리와 a에서 k를 거쳐 b로 가는 거리 중 어느 것이 더 짧은지 비교 후 가장 작은 값을 DP에 저장한다.

플로이드 와샬 동작 과정

초기에 D값을 담을 그래프를 준비하고 테이블을 초기화 한다. 위에서 적었듯, 기본 점화식은 Dab = min(Dab, Dak + Dkb)임을 생각하자. 처음에는 주어진 그래프에서 인접노드만 조사해서 이차원 테이블에 D값을 기록한다. 이후에 각 노드를 거쳐가는 경우를 고려해서 테이블을 갱신할 것이다. 아래 테이블을 보자. 기본적으로 인접 노드에 대한 정보만 기록해놓고(1-2 사이 한 다리 간선만) 두 노드 사이에 간선이 연결되지 않은 경우 무한대로 넣는다.

 

이후에 모든 노드에서 다른 모든 노드로 가는 경우에 대해서 반드시 1번 노드를 한 번 거쳐갈 때를 고려해 테이블을 갱신한다. 위의 테이블에서 바뀐 것을 볼 수 있다.

이를 2, 3, 4번 노드에 대해서도 진행해주면 최종적으로 모든 노드에 대해서 최단거리를 구할 수 있다.

위에서 모든 노드에 대해 출발점, 경유점, 도착점을 바꿔주기 때문에 각 점을 고르는 경우가 n가지이니 시간복잡도가 O(n**3)이된다.

 

 

2. 동전 2 (#2294)

 

동전 2 문제는 풀이를 보고 깜짝 놀랐던..생각보다 엄청 간결하게 풀 수 있더라. 핵심은 DP 개념인데, DP는 여전히 친숙하지 않다..

 

이 문제는 전형적인 DP 문제이다. 동전으로 만들 수 있는 가장 작은 값부터 하나씩 쌓아 올리는 개념이다. 다른 풀이를 검색해보면 설명이 간결해 잘 이해가 되지 않았는데, 예시를 보면 바로 이해가 된다.

 

문제에서 주어진 동전은 1, 5, 12이다. 이걸로 1부터 하나씩 값을 만들어본다고 해보자.

먼저, 값을 저장할 배열 dp를 만든다. dp의 길이는 인덱스 0부터 10000까지 총 10001로 설정한다. 문제에서 만들고자 하는 값 k의 최대치는 10000이니, 모든 dp 배열에 10001을 먼저 대입해준다. 이렇게 해주는 이유는, dp의 점화식이 아래와 같기 때문이다. 

 

dp[i] = min(dp[i], dp[i-c]+1) (c는 코인 값)

 

자, 이해가 여전히 안될 테니 예시로 가보자. 우리는 가진 동전으로 0을 절대 만들 수 없으니, dp[0] = 0으로 배정한다. 이제 1을 만든다고 해보자. 현재 dp[1] = 10001이다. 그런데 우리는 동전 1이 있으니 이 한 개를 이용하면 된다. 따라서 dp[1-1]+1= 1이다. 앞의 dp[1-1]은 동전 1을 쓰기 직전까지의 저장된 dp값이고 여기에 동전 1을 쓰면 동전 개수가 +1이 된다.

 

다음 예시를 보자. 2를 만든다. 동전 1만 써야하니 dp[2] = min(10001, dp[2-1]+1)이다. 왜 dp[2-1]+1이냐? 2를 만들려면 숫자 2에 가진 코인 값 1만큼 빼줬을 때 저장된 dp값에다가 동전 하나를 추가하면 그것이 dp[2]가 된다. 이를 모든 동전에 대해서 해주면 그 중 가장 작은 값이 dp에 저장된다.

 

14를 만들려면 dp[13]에서 코인 1짜리 1개만 더 쓰면 된다. dp[17]은 dp[12]에서 코인 5짜리 1개만 더 쓰면 된다. 이런 식으로 앞에 저장된 dp를 불러오기 위해 인덱스 값에 코인 값만큼 빼주고 코인 한 개만 쓰는 식으로 값을 불러오는 개념이다.

 

전체 코드는 아래와 같다.

 

from sys import stdin

n, k = map(int, stdin.readline().split())

coins = sorted([int(stdin.readline())for _ in range(n)])

dp = [10001] * 10001
dp[0] = 0

for i in range(1, k+1):
    for c in coins: # 코인 하나씩 값을 뽑아온다.
        if i < c:
            break
        dp[i] = min(dp[i], dp[i-c]+1)

print(dp[k] if dp[k] != 10001 else -1)

 

참조 풀이: https://suri78.tistory.com/189