import queue 내장된 queue 라이브러리를 사용한다. 선언할 때 크기를 지정할 수 있다. Queue(2) push → put() pop + top → get() 위 라이브러리에는 PriorityQueue도 있다. 우선순위를 부여하여 가장 큰 요소를 먼저 제거하는 구조이다. 튜플을 이용하여 정렬할 수 있다. q.put((3, "Apple")) q.put((1, "Banana")) q.put((2, "Cherry")) print(q.get()[1]) # Banana print(q.get()[1]) # Cherry print(q.get()[1]) # Apple Priority Queue는 모두 시간복잡도가 $O(logN)이다.$

https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 이전에 풀었던 주식 문제와 유사하되, 조금 더 어려운 문제이다. 왜냐하면 주식에서는 단편적으로 주식 가격을 파악하면 되었지만 이제는 기둥의 길이가 서로 영향을 주기 때문에 어렵다.. 천막을 치는 패턴을 파악했어야 했는데, 여기서 나의 큰 실수가 있었다. 천막 높이의 갱신하는 점이 단순히 우상향인 줄 알았는데, 만약 우하향으로 되는 방식도 고려해야 한다. 이걸 어떻게 처리해야하나 고..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 해결 방법 다 고안해놓고 괜히 10만 개 정도는 배열에 못 넣는 줄 알고 돌아 돌아 접근했다. 알고보니 배열에 넣을 수 있더라...? 여기서 주식을 통해 이익을 최대화하는 방법은 주식을 가장 싸게 사서, 가장 비싸게 파는 것이다. 여기서 앞에서부터 주식을 사고, 팔았는데 만약 나중에 더 높은 주식 가격이 나온다면...? 곤란하다. 그래서 이런 점을 해소하기 위해 뒤에서부터 높은 ..

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 으 으 으 왕바보! 가장 빠른 탈출 시간을 출력하면 되기 때문에 BFS를 쓰면 쉬운 문제처럼 보이나 은근 까다로웠던 문제이다. 여기서 핵심은 불의 확산이다. 단계별로 불을 확산해야 하는데, 처음에는 한 배열에 불로만 표시하려고 불 여부만 판단하고 이를 상하좌우로 확산했다. 그런데 현재 단계와 이전 단계들의 구분이 없어져서, 결국 한 단계만에 모든 빈칸에 불이 확산되는 꼴이 되어버렸다..

앞서 살펴본 AVL 트리는 이진 탐색 트리이나, 이제 살펴볼 트리들은 nonbinary tree이다. 스택 오버플로우에 의하면 AVL 트리는 인메모리 시에 랜덤 액세스가 상대적으로 cost가 적어 유용하지만, 디스크에 저장되는 경우에는 B-Tree가 유용하다고 한다. AVL 트리는 기본적으로 많은 양의 데이터를 저장하는 용도는 아니다. 그래서 데이터베이스에서 주로 인덱스 시에 B 트리를 활용하는 것인가... (FYI. 해시테이블이 인덱스로 쓰일 수 있으나, 주로 등호 연산만 가능하고, 부등호 표현은 불가능하기 때문에 비효율적이다.) B트리는 2개 이상의 child를 가질 수 있기 때문에 용량이 상대적으로 방대한 편이다. B-트리는 탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 Balanced Tre..

이진탐색트리는 쏠림현상이 발생할 경우 (최악의 경우) 탐색 시 시간 복잡도가 $O(N)$이다. 이러한 경우를 방지하기 위해 AVL 트리를 고안해냈다. 특징은 다음과 같다. 1. 이진 탐색 트리의 속성을 가진다. 2. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다. 3. 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다. 4. 삽입, 검색, 삭제의 시간 복잡도가 $O(logN)이다. (N = 노드의 개수)$ AVL 트리의 전반적인 작동을 시뮬레이션 해볼 수 있는 유용한 사이트이다.(백문이 불여일견) https://www.cs.usfca.edu/~galles/visualization/AVLtree.html AVL Tree Visualzation www.cs.usf..