SW사관학교 정글7기 개발일지 (08/22)

c4fiber·2023년 8월 22일

TIL baekjoon

SW사관학교 정글7기

목록 보기

14/49

백준 풀이

1916 최소비용 구하기

접근

최단거리 최소비용 탐색 알고리즘인 다익스트라(Dijkstra) 활용

dfs를 통해 완전탐색을 수행하고 그 과정에서 소요된 cost를 계산하는 방식으로 접근했다.

풀이

import sys
input = sys.stdin.readline
from heapq import heappush, heappop
INF = int(1e9)

# 시작지점과 가장 거리가 짧은 노드를 반환한다.
def get_shortest_node():
    min_distance = INF
    index = 0
    for i in range(1, N+1):
        if not visited[i] and distance[i] < min_distance:
            min_distance = distance[i]
            index = i
    return index

# Dijkstra
def dijkstra(start):
    # start 부터 방문 시작
    distance[start] = 0
    visited[start] = True

    hq = []
    heappush(hq, (0, start))

    # 시작노드를 제외한 N-1개의 노드 방문
    while hq:
        now_distance, now = heappop(hq)

        # distance값이 더 작다 => 이전에 이미 갱신되어서 의미 없는 값이다.
        if distance[now] < now_distance:
            continue

        for next, cost in graph[now]:
            if distance[next] > now_distance + cost:
                distance[next] = now_distance + cost
                heappush(hq, (distance[next], next))



N = int(input())
M = int(input())
graph = dict((node, []) for node in range(1, N + 1))

# input: cost
for _ in range(M):
    u, v, c = map(int, input().split())
    graph[u].append([v, c])

start, end = map(int, input().split())

# variables
visited = [False] * (N + 1)
distance = [INF] * (N + 1)

dijkstra(start)
# print(f'distance: {distance}')
print(distance[end])

후기

다익스트라 알고리즘은 접한 기억이 꽤 많았는데 제대로 구현하지도 못하고 설명하지도 못했다.

알았다! 라고 확신하고 넘어가는 행위가 얼마나 무서운지 알게되었다.

2294 동전2

접근

처음 접근하는 방법은 백트래킹이였다. 하지만 최악의 경우 완전탐색을 수행하므로 최악의 경우 시간이 너무 오래걸릴 것이라 생각했다.

시간 복잡도를 계산하기가 어려워서 추측하기로는 O(nlogn)정도로 생각하고 있다. (모든 코인의 종류 N을 각각 logN 만큼 결정트리를 따라 내려가야 하므로)

풀이

import sys
input = sys.stdin.readline
from collections import defaultdict


def select_coin(k, coins):
    # default dictionary 기본값을 10001로 설정
    dp = defaultdict(lambda: 10001)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, k + 1):
            # i원을 만들기 위해 필요한 동전 개수는 i-coin원을 만들기 위한 코인 개수 + 1
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    # 최소값이 한 번도 변경된 적 없다 == 주어진 동전을 이용해 k원을 만들 수 없다.
    if dp[k] == 10001:
        print(-1)
    else:
        print(dp[k])


n, k = map(int, input().split())
coins = []

# input
for i in range(n):
    coins.append(int(input()))

# main
select_coin(k, coins)