시나위

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 그리디 알고리즘으로 풀었다. 강의 시간을 정렬한 다음 모든 강의 시간을 순회하면서 힙 answer에 데이터를 추가하거나 수정하는 방식이다. 추가하는 시간은 해당 강의실의 강의가 끝나는 시간을 나타낸다. python의 heap은 최소힙이므로 0번째(top)가 최솟값이 되고 항상 모든 강의실 중 가장 빨리 끝나는 시간을 나타내므로, 강의실을 계속 사용해도 되는지 아니면 하나 더 사용해야하는지 판단할수 있다. import sys; input = sy..

https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 두 개의 힙(최대힙, 최소힙)을 사용해서 최대값 최솟값을 같이 파악하고, 출력할때 힙에서 제거했던 값이면 빼내는 방법으로 진행한다. 한번 제거했다가 같은 문제번호가 난이도가 바뀌어서 추가하는 경우 따로 처리해줘야했는데 level이라는 딕셔너리를 사용해서 현재의 난이도를 추적할수 있도록 했다.(힙에 같은 문제로 이전 난이도를 가지고 있다면 제거할수 있도록) import..

https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 이 문제는 s에서 출발해서 t까지의 최소 가중치를 구하는 문제이다. 다익스트라를 사용하면 쉽게 구할 수 있다. #include #include #include using namespace std; #define INF 1234567890 int dijkstra(int start, int end, int size, vector linked_list) { int cur, cur_dist, adj..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr from heapq import heappush, heappop def solution(operations): answer = [0, 0] min_h, max_h = [], [] number_in_heap = dict() for op in operations: if op[0] == 'I': # 숫자 삽입 _, num = op.split() num = int(num) heappush(min_h, num) heappush(max_h, -num) if not number_in_heap.get(num): number_in_heap[num] = 0..

https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr from heapq import heappush, heappop def solution(jobs): # jobs가 정렬이 안되어있음 jobs.sort(key=lambda x: (x[0], x[1])) # 0 변수 선언 min_h = [] jobs_idx = 0 cur = 0 s, rt = None, None running = False answer_list..

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 from collections import deque def solution(N, road, K): INF = 5000000 g= [[] for _ in range(N + 1)] dist = [INF] * (N + 1) for i in range(len(road)): g[road[i][0]].append((road[i][1],road[i..