이모저모

- 문제: https://leetcode.com/problems/network-delay-time/ - 코드 class Solution(object): def networkDelayTime(self, times, n, k): # 초기화에 사용할 큰 수 INF = int(1e8) # 각 노드 간 간선과 간선에 해당하는 시간(가중치)에 대한 정보를 2차원 배열에 반영 graph = [[] for _ in range(n+1)] for time in times: graph[time[0]].append((time[1], time[2])) # 각 노드에 이르는 최소시간을 적어놓을 1차원 배열 mins = [INF] * (n+1) def dijkstra(start): # 최소 시간인 경로부터 뽑기 위해 heapq 준..

import heapq import sys n, m = map(int, sys.stdin.readline().split()) con_info = [[] for _ in range(n+1)] for _ in range(m): s, e = map(int, sys.stdin.readline().split()) con_info[s].append(e) con_info[e].append(s) # 출발점에서 각 노드(헛간)에 이르는 최단거리 테이블 준비 (INF 로 초기화) INF = int(1e9) min_dis = [INF] * (n+1) min_dis[1] = 0 # 해당 시점마다 출발지로부터 가장 가까운 노드들을 가져와서, 그 노드를 경유하는 루트를 고려할 것 # 가까운 것부터 가져오기 위해 최소힙 사용 qu..

1. 문제 2. 코드 import heapq import sys # n X n 의 탐사 지형(?) 정보 받아와서 2차원 배열로 그리기 n = int(sys.stdin.readline().rstrip()) graph = [[] for _ in range(n)] for i in range(n): row = list(map(int, sys.stdin.readline().split())) graph[i] = row # 초기화에 사용할 큰 수 INF = int(1e9) # 아직 접근 가능한 좌표와 경로 전혀 취하지 않았으니까 모든 좌표는 큰 수로 초기화, 시작점은 자신의 칸에서의 소모량으로 초기화 consumption = [[INF] * n for _ in range(n)] consumption[0][0] = g..

문제: https://leetcode.com/problems/cheapest-flights-within-k-stops/ 다익스트라 자체도 낯설고 어려운데, 이 문제는 적절히 가지를 쳐서 시간효율을 챙기지 않으면 리트코드에서 거절당하는 문제였다. 몇 번 더 복습해야겠다! def findCheapestPrice(n, flights, src, dst, K): # 공항 간 연결정보와 비용을 담아두는 곳 # 출발지를 key 로, (도착지, 비용) 튜플들을 원소로하는 리스트를 value 로 하는 dictionary graph = collections.defaultdict(list) for s, d, c in flights: # start, destination, cost graph[s].append((d, c)) ..

1. 병합정렬 https://jeojeo.tistory.com/125 병합정렬 (merge-sort) _ 후위순회방식의 DFS 병합정렬이 어떻게 이루어지는지를 배웠다. 그 과정에 핵심적으로 작용하는 건 후위순회방식의 DFS였다. 후위순회방식은 언제 쓰이는가 생각해보면, 즉, 각 레벨에서 동일한 패턴의 작업을 해야 jeojeo.tistory.com 2. 퀵정렬 https://jeojeo.tistory.com/126 퀵정렬(quick sort) - 전위순회방식의 DFS 0. 병합정렬 vs 퀵정렬 퀵 정렬(quick sort)을 공부했다! 이건 병합정렬처럼 재귀적 구조를 가지기는 하지만, 확연히 다른 점이 있다. 바로 "전위순회방식"을 취한다는 점. 즉 자기 레벨에서 지정된 jeojeo.tistory.com ..

문제 : https://programmers.co.kr/learn/courses/30/lessons/43238 코드 def solution(n, times): answer = int(1e18) # mid 의 움직임에 따라 총 심사시간이 상정되면, 그 안에 몇 명까지 심사가능한지 구하는 함수 # 이 값을 가지고 심사시간을 늘려야 할지 줄여도 될지 판단할 것 def how_many(limit): total = 0 # 각 심사위원이 걸리는 시간으로 총 심사시간을 나누어서 구한 각각의 몫들을 더한다. # 모든 심사위원이 빈틈없이 계속 사람을 받을 경우를 나타냄. for time in times: total += limit//time return total # 최소 1분, 최대는 모든 사람을 모든 심사위원이 동일..