컴공댕이 공부일지

🔎 우선순위 큐란? 기존의 큐는 먼저 넣은 요소가 먼저 나오는 FIFO( first in - first out )이지만, 우선순위 큐는 들어간 순서 상관없이, 우선순위가 높은 데이터가 먼저 나온다 ! (ex.위급한 사람부터 처치하는 응급실) 우선순위 큐는 힙(Heap)이라는 자료구조로 구현하며, 모든 연산에 대한 시간 복잡도가 O(log n)이다. 📖 완전 이진 트리와 힙 🔎 완전 이진 트리 (complete binary tree) - 이진 트리(자식이 최대 2개인 트리)의 한 종류 - 마지막 레벨 제외하고는 모든 레벨이 다 채워져있어야 함 - 마지막 레벨의 모든 노드는 왼쪽부터 빈공간없이 채움 📍 힙(Heap)의 조건 1) 완전 이진 트리 2) 힙은 상위노드가 모든 하위노드보다 우선순위가 크거나 같다 ..

🔎 그리디 알고리즘(탐욕법)이란? 전체 문제를 여러 조각으로 분할하고, 각 단계별 최적해를 결합해 최종 최적 해를 만들어가는 알고리즘인데, 쪼갠 작은 단계마다 욕심쟁이처럼, 미래는 보지 않고 그저 눈 앞에 보이는 가장 좋은 방법만을 늘 선택합니다. 단순히, 현재 내릴 수 있는 최선의 선택에만 집중하는 알고리즘입니다. 📖 그리디 알고리즘 문제 출제 경향 단순히 각 단계에서 가장 최적의 값을 고르는 그리디 알고리즘이 늘 최적해를 구해내진 못합니다. 근사한 해만을 구할 수 있는 경우가 대부분입니다. 그리디 알고리즘은 계산 속도가 빠르기에, 시간 및 공간적 제약으로 최적해를 구하지 못해서 최적해 대신 근사해를 구해야 할 때 사용됩니다. 그러나, 이 경우는 주로 코딩테스트에서 출제되진 않고, " 탐욕법을 사용해도..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.