코딩스토리

www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 알고리즘 기말 공부를 하다가 갑자기 꽂혀서 풀어보았어요.. 분명 구글에 red-black-tree의 유일성을 찾아보고 있었는데 뭐지..? 어쨌든 최소 스패닝 트리는 두 가지 방법으로 구할 수 있다. 프림 알고리즘 크루스칼 알고리즘 둘 다 이산수학, 자료구조 시간에 배운 알고리즘인데 거의? 비슷하다. 나는 프림 알고리즘으로 풀었으니까 프림 알고리즘에 대해 설명해보자면..

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 23장 우선순위 큐와 힙에 나온 내용을 바탕으로 작성하였습니다. 개요 우리는 기존에 "큐(Queue)"라는 자료구조를 배웠었다. 큐는 스택과 비슷한 자료구조로 '선입선출'이라는 형태를 갖추고 있다. 그렇다면 우선순위 큐와 큐의 차이점은 무엇일까? 바로 '우선순위', 즉 선입선출 구조이나 '우선순위'대로 원소를 꺼낼 수 있다는 점이다. 우선순위를 만족하게 정렬하려면 여러가지 방법이 있다. 가장 단순한 방법은 O(n)이라는 시간에 모든 원소를 비교해서 정렬할 수 있다. 하지만 당연히 이 방법은 사용하지 않을 것이다. 이진 탐색 트리(Binary Search Tree)를 사용하면 O(logn)의 시간에 정렬할 수 있지만 이는 책의 표현을 빌려 쓰자면 "닭 ..

백준 11000번 - 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 이 문제는 우선순위 큐를 사용한 문제이다. 처음 문제를 풀 때 실수했던 점은 입력을 받을 때 정렬되서 들어온다고 생각한 것이였다. (사실 생각한게 아니고 아무 생각없이 그냥 알고리즘만 생각해서 풀었따ㅎ) 그래서 한번 입력받을 때마다 우선순위 큐의 top과 비교해서 정답을 도출했는데 당연히 틀렸다. 고민하다가 생각난 풀이법이 우선순위 큐(Priority queue)를 두 개 사용하는 방법이다! 첫 번째 큐에는 모..