문제 설명 문제 풀이 가장 멀리 떨어지 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다는 부분에서 다익스트라 최단 경로 알고리즘을 사용해야겠다고 생각했다. 전체 코드 import heapq def dijkstra(start): q = [] # 시작 노드로 가는 최단경로는 0 heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist + i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (co..

문제 설명 문제 풀이 모든 별은 서로 직/간접적으로 이어져 있어야 하고, 별자리를 만드는 최소 비용을 구해야 한다고 해서 그래프 문제, 그중 최소 신장 트리 알고리즘을 사용하는 문제라고 생각했다. * 신장 트리(Spanning Tree): 하나의 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프. 최소 신장 트리는 신장 트리 중에서도 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘이다. 최근에 이코테에서 크루스칼 알고리즘에 대해 공부했기 때문에 이를 적용해보기로 했다! 크루스칼 알고리즘(Kruskal Algorithm)의 과정은 다음과 같다. 1) 간선 데이터 오름차순으로 정렬하기 2) 간선을 확인하며 2-1) 사이클이 만들어지면 pass 2-2) 사이클이 만들어지지 않으면 최..

문제 설명 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제 풀이 작업의 요청부터 종료까지 걸린 시간의 평균을 최소로 만들어야하는, 즉 SJF(Shortest-Job-First) 스케줄링을 비선점형 방식으로 구현하는 문제였다. 마침 운영체제에서 스케줄링 기법을 공부하고 있었던 터라 반가웠던 문제❕ 스케줄링에 관한 내용은 아래에서 확인 [운영체제] 4. CPU 스케줄링 | KOCW 2017 이화여대 반효경 교수님 * 강의를 듣고 복습하며 정리한 내용입니다. CPU 프로그램의 기계어 명령을 수행하는 컴퓨..

문제 풀이 from collections import deque F, S, G, U, D = map(int, input().split()) visited = [0] * (F + 1) def bfs(visited, v): queue = deque([v]) dx = [U, - D] while queue: x = queue.popleft() if x == G: break for i in range(len(dx)): # 해당하는 층이 없을 때 움직이지 않는다 if dx[i] == 0: continue nx = x + dx[i] if 0 역시 엘리베이터 버튼을 누르지 않아도 된다(반복문에서 continue) 5014번: 스타트링크 첫째..

문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우 P처럼 소수 양쪽에 아무것도 없는 경우 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다. 예를 들어, 101은 P가 될 수 없습니다. 예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진..