Redddy's Devlog

레벨 인터뷰 하면서 받았던 피드백을 반영해보자 세웠던 액션 플랜을 준비하기 위한 글이다.    나는코더다에서 카드 게임(Easy)와 카드 게임(Hard)라는 문제가 나왔다.  Easy문제 요약Easy는 상대의 체력 $H$와 내가 가지고 있는 공격력 카드 $N$장과 그리고 각 공격력 카드의 공격력 $d_i$이 주어진다. 카드를 사용하면 상대의 체력은 $d_i$ 만큼 깎이고, $H$가 0이하가 되면 게임은 끝난다. 그리고 각 카드는 한번씩만 사용할 수 있다. 최대한 많은 카드를 사용고자할 때 최대 몇 개의 카드를 사용할 수 있는지를 구하는 문제이다. 모든 카드를 사용하여도 $H$를 만들지 못하면 -1을 반환한다. 문제 접근정리하면 최대한 많은 카드를 사용하여 $H$ 이상을 만들어야 한다. $H$ 이상을 만들..

우선순위 큐는 내부적으로 힙(heap)이라는 완전이진트리 Complete binary Tree로 되어 있다. 힙 트리의 루트 노드(root node)에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데, 전자는 최대힙(max-heap), 후자는 최소힙(min-heap)이라 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(log N)이다. 무작위 숫자들을 힙에 전부 넣고 하나씩 빼면 정렬된 결과를 얻을 수 있는데, 이게 힙정렬이다. from queue import PriorityQueue pq = PriorityQueue() pq.put(123) pq.put(789) p..