728x90 반응형 Computer Science/자료구조 & 알고리즘20 [자료구조 & 알고리즘] 힙(Heap)으로 우선순위 큐 구현하기 (feat. Lazy Deletion) 힙(Heap)으로 우선순위 큐 구현하기 (feat. Lazy Deletion)우선순위 큐(Priority Queue)는 우선순위가 높은 요소가 먼저 처리되는 자료구조입니다.일반적인 큐(Queue)는 선입선출(FIFO) 방식이지만, 우선순위 큐는 우선순위(priority) 에 따라 요소가 처리됩니다.우선순위 큐를 효율적으로 구현하려면 힙(Heap)을 활용하는 것이 가장 적절합니다.이번 글에서는 힙(Heap)을 사용하여 우선순위 큐를 구현하는 방법을 살펴보겠습니다. 🔹 1. 우선순위 큐(Priority Queue)란?우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지며, 우선순위가 높은 요소가 먼저 처리되는 자료구조입니다.즉, 일반적인 선입선출(FIFO) 방식의 큐와 다르게 요소의 우선.. 2025. 2. 25. [자료구조 & 알고리즘] AVL 트리 (feat. 균형 이진 트리) 2025.02.07 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 이진 검색 트리 (feat. 트리) 균형 이진 트리(Balanced Binary Tree)란?균형 이진 트리(Balanced Binary Tree)는 이진 트리(Binary Tree)의 한 종류로, 트리의 높이를 일정하게 유지하여 탐색, 삽입, 삭제 연산의 시간 복잡도를 O(log n)으로 보장하는 자료구조입니다. 이진 검색 트리(Binary Search Tree, BST)는 트리가 한쪽으로 치우칠 경우 탐색 시간이 O(n)까지 증가할 수 있기 때문에, 이를 해결하기 위해 균형을 유지하는 트리가 필요합니다.대표적인 균형 이진 트리에는 AVL 트리와 레드-블랙 트리가 있습니다. 이번에는 AVL 트리.. 2025. 2. 13. [자료구조 & 알고리즘] 이진 검색 트리 (feat. 트리) 자료구조 관련 내용은 하단 포스트를 참고해주세요.2024.12.14 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가) [자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가)1. 선형 리스트 (Linear List)설명: 데이터를 연속된 메모리 공간에 저장하며, 순서를 보장하는 자료구조.특징:인덱스를 통해 O(1) 시간 복잡도로 접근.삽입/삭제는 O(n)로 비효율적.필수 알고리즘:이rnasterofmysea.tistory.com 0. 이진 트리 (Binary Tree)설명: 각 노드가 최대 두 개의 자식을 가지는 계층적 자료구조.특징:전위, 중위, 후위 순회 가능.필수 알고리즘:트리 순회:전위, 중위, 후위 탐색.최대 .. 2025. 2. 11. [자료구조 & 알고리즘] 해시 테이블(Hash Table) 오랜만에 자료구조 시간이 돌아왔습니다. ㅎㅎㅎ영어가 가능하신 분들께서는 해당 포스트 참고하시면 도움이 많이 될 것 같습니다! 학습 자료 & 이미지 (GIF 출처): https://junminlee3.medium.com/hash-tables-animations-that-will-make-you-understand-how-they-work-d1bcc850ba71 Hash Tables — animations that will make you understand how they workHello, today we’re going to talk about things like how hash tables work, and about hash functions, collisions etc. After knowing.. 2025. 2. 5. [자료구조 & 알고리즘] 이분 탐색 (Binary Search) 이분 탐색 (Binary Search) 알고리즘이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘입니다. 탐색 범위를 절반으로 줄이기 때문에 시간 복잡도가 O(logN)O(\log N)으로 매우 빠릅니다. 이번 포스트에서는 이분 탐색의 개념, 동작 방식, 그리고 C 언어로 구현한 예제를 자세히 설명합니다.1. 이분 탐색이란?이분 탐색은 데이터를 절반씩 나누며 탐색 범위를 좁혀가는 방식으로 동작합니다. 이 과정은 반복적으로 수행되어 결국 원하는 값에 도달하게 됩니다.단, 데이터가 반드시 정렬되어 있어야 한다는 전제 조건이 있습니다.2. 이분 탐색의 동작 과정배열의 중간 값을 선택합니다.중간 값이 찾고자 하는 값과 같으면 탐색을 종료합니다.중간 값이 찾고자 하는 값보다 .. 2025. 2. 3. [자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘(Greedy Algorithm)1. 개요그리디 알고리즘(Greedy Algorithm)이란 현재 단계에서 가장 최적의 선택을 반복하여 문제를 해결하는 알고리즘입니다. 탐욕법이라고도 불리는 이 방식은 매 순간 최선의 선택이 결국 전체 문제의 최적해로 이어진다고 가정합니다.이 접근법이 성공적으로 작동하려면 문제에 대한 몇 가지 조건이 만족되어야 합니다. 그렇지 않으면 전역 최적해(Global Optimal Solution)를 보장하지 못할 수 있습니다.2. 그리디 알고리즘의 조건Greedy 선택 속성 (Greedy Choice Property)각 단계에서의 선택이 이후 단계에 영향을 주지 않고, 그 순간 최적의 선택을 하면 전체 최적해에 도달할 수 있는 속성을 의미합니다.최적 부분 구조 (O.. 2025. 2. 2. 이전 1 2 3 4 다음 728x90 반응형
