코딩 테스트48 [백준 15486번] 동전 1 문제풀이 이전에 풀던 문제는 다이나믹 프로그래밍을 이용해 최소 개수나 최대 개수를 구하는 것이었는데, 이 문제는 경우의 수를 구하라는 면에서 달랐다. 다이나믹 프로그래밍을 이용해 어떻게 값을 저장해야 좋을지 고민하였다. 가치 k가 되는 경우의 수 문제를 가치 i (1 2023. 8. 1. [백준 15486번] 퇴사 2 문제풀이 날짜당 걸리는 시간과 받을 수 있는 가격을 저장한 후, 다이나믹 프로그래밍을 통해 1번째날부터 받을 수 있는 가장 큰 값을 저장한다. import sys n = int(sys.stdin.readline()) time = [0 for i in range(n)] price = [0 for i in range(n)] max_price = [0 for i in range(n+1)] for i in range(n): # 시간과 가격 입력 받기 time[i], price[i] = map(int, sys.stdin.readline().split()) for i in range(n): if i + time[i] < n + 1: max_price[i + time[i]] = ma.. 2023. 7. 31. [개념] 최단 경로 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘으로, '길 찾기' 문제라고도 불린다. 최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3가지 이다. 이 중, 다익스트라 최단 경로와 플로이드 워셜 알고리즘이 가장 많이 등장한다. 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 적용된다. 1. 다익스트라 최단 경로 알고리즘 : 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 .. 2023. 7. 26. [백준] 2805번 나무 자르기 import sys n,m = map(int, sys.stdin.readline().split()) array = list(map(int, sys.stdin.readline().split())) start = 0 end = max(array) while start 0: result += i - mid if result < m: # 필요한 길이보다 result가 작으므로, 잘린 나무가 더 길어져야 한다. end = mid - 1 else: start = mid + 1 print(end) 입출력은 동일했으나, 시간초과 결과가 나왔다. import sys n,m = map(int, sys.stdin.readline().split()) array = list(map(int, sys.stdin.readline().. 2023. 7. 25. 이전 1 ··· 8 9 10 11 12 다음
