국문과 유목민

1. 문제 설명 N개의 강의 중 선수 강의가 있을 경우 특정 강의가 주어졌을 때, 해당 강의를 듣기 위해서 걸리는 최소한의 시간을 구하는 문제 - 위상정렬을 이용하는 문제로 위상정렬 이론에서는 리턴하는 값이 순서였다면, 이번에는 cost이다. 하지만 알고리즘 상에서 큰 변경점은 없다. 단지, 시간의 정보를 담은 리스트 변수가 하나 필요하다. 또한, 초기 input값 처리 부분을 고려하면 될 것으로 보인다. 2. 코드 from collections import deque import copy n = int(input()) indegree = [0]*(n+1) graph= [[] for _ in range(n+1)] time = [0]* (n+1) # 방향 그래프의 간선 정보 입력 받기 for i in ra..

1. 문제 설명 마을을 2개로 나누려고 하는데 가장 효율적으로 나눌 수 있는 방법을 찾는 문제 - 핵심 아이디어는 전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다. - 마을을 2개로 나누는 방법은 모든 그래프를 다 잇고난 이후 비용이 가장 큰 간선을 제거해주면 된다. - 정리하자면 크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중 가장 비용이 큰 간선을 제거하는 것이다. 2. 코드 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(pare..

이코테 스터디를 시작한 지 2일차로 어제 하지 못했던 다른 알고리즘 이론들을 복습하고, 블로그에 정리했다. 오늘 복습한 알고리즘 이론의 경우 정렬, 탐색, 다이나믹프로그래밍, 최단경로, 그래프이론 정도이다. 아직 책의 이론 부분에 나온 문제 풀이였지만 막상 정리해보니까 꽤나 문제가 많았다는 것을 다시 한 번 느낀 것 같다. 내일은 알고리즘 정리한 것들 중 어려웠던 부분들을 안 보고도 구현해보고자 한다. 아니면 프로그래머스 lv1에 해당하는 이전에 풀었던 문제들을 다시 한 번 풀어도 좋을 것 같다. 추가적으로 부스트 캠프 pre-course가 5시간 정도 남은 것 같은데 이것도 들어야 해서 시간 배분이 조금 고민이다. 오늘 한 일 - 정렬, 탐색, 다이나믹프로그래밍, 최단경로, 그래프이론 복습 _ 티스토리..

1. 문제 설명 팀을 결성하기 위해 학생과 학생을 묶고, 학생과 학생이 같은 팀인지 확인하는 문제. - 학생들을 같은 팀으로 묶는 함수가 존재하고(union_parent), 학생들이 같은 팀인지 확인하는 함수가 존재한다.(same_parent) 2. 코드 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b def same_parent(pa..

1. 문제 설명 도시와 도시가 연결되어 있을 때 전보를 보내는 경우 얼마나 많은 도시에 보낼 수 있으며, 가장 먼 거리는 얼마인지 구하는 문제이다. - 다익스트라 알고리즘을 활용한 문제로 heapq를 활용한다. 2. 코드 import heapq # 입력 INF = int(1e9) a, b, start = map(int, input().split()) graph = [[] for _ in range(a+1)] distance = [INF]*(a+1) for _ in range(b): x, y, z = map(int, input().split()) graph[x].append((y, z)) # 노드, 거리 # 다익스트라 알고리즘 def dijkstra(start): q = [] heapq.heappush(q..