소소한필통

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net About Problem 문제의 핵심은 저 두줄이다. 간선의 정보를 주고 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 것이다. 간선의 비용이 양수이며 다르고 최소 비용을 구하는 알고리즘은 다익스트라 알고리즘이다. 간선의 최단경로를 구하는 알고리즘은 다음과 같다 Code 코드 설명은 코드 주석으로 적었다. from sys import stdin..

문제 https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr Prolem About 핵심 키워드 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려 고 합니다. 위 문장으로 이뤄 봤을 때 가중치가 각각 다른 그래프 중 최단경로를 구해야 하므로 다익스트라 알고리즘을 써야한다. 아래의 그림으로 최단경로를 구하는 문제에서 어떤 알..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 설명. 문제는 핵심 1. 현재 택시 위치에서 연료내에 갈 수 있는 손님 중 가장 가까운 손님을 선택 2. 가장 가까운 손님이 겹칠 때, 행이 작은 손님 선택, 이것도 겹칠 때 열이 작은 손님을 선택 3. 연료내로 목적지 갈 수 있는지 판단하고 손님에서 목적지까지 가는 연료량을 다시 충전하기. Edge Case 1. *edge 첫 택시 위치에 손님이 있을..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 설명 주어진 랜선(K)개를 통해서 길이가 똑같은 랜선(N)개를 만들 때 최대 길이를 구하는 문제이다. Input input값을 통해서 어떤 알고리즘을 쓸건지 판단한다. 이 문제는 K는 10000 이하의 자연수고 N은 1000000이하의 자연수다. 그러므로 완전 탐색은 못하고 탐색중에 시간 복잡도를 줄이는 탐색이 필요하다. 그래서 저는 값을 찾기 가장 간단한 방법인..

https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 이 문제 설명의 키워드는 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매와 같다. 결국 보석 종류가 다 포함된 가장 짧은 구간을 찾으면 된다. 나의 풀이 ( 효율성 3개 실패) def solution(gems): # 중복이 제거된 보물 리스트 bomul = list(set(gems)) # 보물 딕셔너리 bomul_dict = {} # 최소값 찾기 min_value = 1000..