목록코딩 테스트 (186)
미소를뿌리는감자의 코딩
https://leetcode.com/problems/network-delay-time/description/ Network Delay Time - LeetCode Can you solve this real interview question? Network Delay Time - You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the tar leetcode.com 1. 접근 방법 이번 문제는 Dijkstra 문제로, Dijkst..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1. 접근 방법 자를 수 있는 제일 작은 랜선의 길이 = 1 자를 수 있는 제일 큰 랜선의 길이 = max(lines) 가 될 것이다. 이후 이를 기준으로 binary search를 진행하였다. 2. 코드 def max_length(lines, n): max_line = max(lines) min_line = 1 while min_line
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 접근 방법 이 문제의 경우 2 방법으로 접근하였다. 첫 번째 방법) 최대 height를 나무들 중에서 제일 높은 나무로 정한다. 이후, height -= 1을 해가면서 적정한 height를 찾는다. 하지만, 이런식으로만 구성을 하게 되면 시간 초과가 나게 된다. 만약 현재 height에서 구한 남은 나무의 길이와 m의 차이가 현재 남아 있는 나무의 개수..
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 1. 접근 방법 이 예제를 예로 들어서 설명을 해볼 것이다. 국가예산의 총액이 485 이므로, 총 지방 예상의 예산 요청 수(4)로 나눈다. 이걸 하기로 한 이유는, 예산 요청과 관계 없이, 국가 예산이 다른 지방 예산들에게 나누어 줄 수 있는 예산의 최대값을 구해보고 싶었기 때문이다. 486/4 = 121.25 이다. 평균보다 지방 예산 요청이 낮은 경우, 120, 110은 afford 할..