CS46 [백준] 11000: 강의실 배정 python 구현 / Priority Queue 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 풀이 우선순위큐 알고리즘을 사용하여 1. 현재 수업 끝 시간 2. 다음 수업 시작 시간, 두 가지를 비교하여 구할 수 있다. 우선순위 큐를 쓰는 이유는 최소 힙을 사용하여 비교하게 될 현재 수업 끝 시간의 리스트를 계속 sorting해줄 수 있다. (아마도 내가 이해하기로는..) 리스트로 받은 수업 시간들을 정렬 (시작 시간.. 2023. 4. 12. 우선순위 큐(Priority Queue)가 뭔데 ! https://www.youtube.com/watch?v=AjFlp951nz0 우선순위 큐 (Priority Queue) 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 큐를 구현 하는 방법 리스트를 이용하여 구현 - 삽입: $O(1)$, 삭제: $O(N)$ 힙(heap)을 이용하여 구현 - 삽입: $O(logN)$, 삭제: $O(logN)$ Heap으로 구현하자.. N개의 데이터를 모두 힙에 넣었다가 꺼내면: $O(NlogN)$ 힙(Heap)이 뭔데.. 힙은 완전 이진 트리 자료구조의 일종 힙에서는 항상 루트 노드(root node)를 제거 최소 힙 (Min heap) 루트 노드가 가장 작은 값을 가짐 값이 작은 데이터를 우선적으로 pop !(제거) 최대 힙 (Max heap) 루트 노드가.. 2023. 4. 12. [백준] 16953: A→B python 구현 / Greedy, BFS 문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 풀이 숨바꼭질 문제들( 숨바꼭질, 숨바꼭질3 )과 매우 유사함 ! BFS로 풀면 된다. 주의 ! A, B (1 ≤ A < B ≤ 109) 를 잘 지키자. CODE from collections import deque A, B = map(int, input().split()) def bfs(n): queue = deque() queue.append((n, 0)) while queue: n, time = queue.popleft() ntime = time + 1 for i in range(2): if not i: num = n .. 2023. 4. 12. [백준] 2638: 치즈 python 구현 / BFS 문제 N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다. ... 이하 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주.. 2023. 4. 12. 이전 1 2 3 4 5 6 7 ··· 12 다음
