알고리즘 문제/단계별로 풀어보기 (백준)

👉🏻 2294번: 동전 2n, k = map(int, input().split())money = [int(input()) for _ in range(n)]dp = [float('inf')] * (k+1)dp[0] = 0for i in range(1, k+1): for coin in money: if i - coin >= 0: dp[i] = min(dp[i], dp[i-coin] + 1)print(-1 if dp[k] == float('inf') else dp[k]) 🤔 왜 이렇게 풀었을까?전형적인 DP 문제입니다. 사실 처음에는 아래처럼 '거스름돈 문제다!!' 생각해서 냅다 그리디로 풀어봤는데, 당연하게도 시간이 초과했습니다.n, k = map(int, inpu..

👉🏻 24444번: 알고리즘 수업 - 너비 우선 탐색 1import sys; input=sys.stdin.readlinefrom collections import deque, defaultdictdef bfs(graph, start, visited): queue = deque([start]) visited[start] = 1 order = 2 while queue: node = queue.popleft() for neighbor in graph[node]: if visited[neighbor] == 0: visited[neighbor] = order queue.append(neigh..