어쩌다데싸

백준을 풀다 보니 심심찮게 등장하는 우선순위큐. 이참에 간단하게 정리하고 넘어가야겠다. 1. 우선순위 큐(Priority)란?1) 개념기본적인 자료구조의 큐(Queue)에 우선순위를 도입한 자료구조가 우선순위 큐(Priority)이다. 즉, 각 값들은 우선순위를 가지고 있고 우선순위가 높은 값부터 처리되는 자료구조이다.  2) 구현방법우선순위 큐는 배열, 연결리스트, 힙(Heap)으로 구현가능하며 이 중 힙으로 구현하는 것이 가장 효율적이다.배열, 연결리스트의 삽입/삭제 시간복잡도 : O(n) 힙의 삽입/삭제 시간복잡도 : O(log2n) - 완전 이진트리 구조이기 때문에!3) Priority Queue vs. HeapqPriority Queue는 Thread Safe하고 Heapq는 Non Safe하다..

목차  https://login-data.tistory.com/24 코딩테스트를 위한 기본 개념 1탄 - 그래프(Graph)코딩테스트를 공부하며 그냥 문제만 풀기도 하고 개념을 보고 공부하기도 했는데, 뭔가 따로노는 느낌이 들었다.문제만 풀다보면 막혀서 답지 보고 그 때는 이해한 것 같아 넘어갔다가 나중에login-data.tistory.com그래프 글에서 이어지는 내용으로, 그래프를 어떻게 탐색하는가 방법에 따른 DFS와 BFS를 정리해보려 한다.DFS와 BFS 각각 방법으로 탐색하는 순서를 비교하기 위해 아래와 같은 그래프가 있다고 하자.  1. DFS (Depth-First Search) : 깊이 우선 탐색영문에서도 알 수 있는 것처럼, DFS는 그래프에서 깊은 부분(자식노드)을 우선적으로 탐색하는..

코딩테스트를 공부하며 그냥 문제만 풀기도 하고 개념을 보고 공부하기도 했는데, 뭔가 따로노는 느낌이 들었다.문제만 풀다보면 막혀서 답지 보고 그 때는 이해한 것 같아 넘어갔다가 나중에 까먹을 때가 많았고,개념을 공부했을 때는 그래서 어떻게 구현하는건데? 하면서 결국 문제를 풀지 않으면 개념을 익히기 어려웠다. 그래서 적어보는 나를 위한 코딩테스트 개념 & 기본코드 간단 정리집. 기본적인 개념을 익혀보고, 기본적인 코드를 익히고, 관련 문제를 정리해본다.   목차 1. 그래프 (Graph) 개념그래프는 실제 세계의 현상이나 사물을 정점(Vertext, 또는 노드(Node))과 간선(Edge)로 표현하기 위해 사용된다. 1.1 관련 용어- 노드 (Node) : 위치를 의미. 정점(Vertex)라고도 함- 간..