STUDY

import heapq def dijkstra(u): # 시작 셋팅 D[u] = 0 q = [] heapq.heappush(q, (D[u],u)) # 정점 갯수 만큼 반복 for i in range(V): # 가중치 최솟값 찾기 min_v = 987654321 now, u = heapq.heappop(q) # 방문 처리 visit[u] = 1 # 인접한 정점 업데이터 for v in range(V): if adj[u][v] != 0 and visit[v] == 0 and D[v] > D[u] + adj[u][v]: D[v] = D[u] + adj[u][v] heapq.heappush(q, (D[v],v)) #######################################################..

최소 회의실 개수 문제 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자. 입력 첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 최소 회의실..

정보 상인 호석 문제 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 사고파는 사람을 의미한다. 호석이는 아직 상인계의 새싹이기 때문에, 초기 투자를 통해서 여러 명의 "정보 고릴라"들로부터 정보를 모으려고 한다. 정보 고릴라란 여기저기서 정보를 수집하는 사람들을 의미한다. 일단 정보를 긁어모으기 위해서 호석이는 여러 정보 고릴라들에게 정보를 구매하려고 한다. 암흑가의 연락망은 빼곡하기 때문에 누가 어떤 정보를 얻었는지에 대한 찌라시들이 수시로 퍼진다. 찌라시로 알 수 있는 것은, 어떤 이름을 가진 고릴라가 C1, C2, ..., Ck 만큼의 가치가 있는 정보 k..

카드 합체 놀이 문제 석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다! 아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y) 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다. 이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 ..