* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 앞선 포스팅에서 살펴 본 이진 탐색 트리를 통한 searching은 일반적으로 시간 복잡도가 O(logN)이다. 그러나, 트리가 불균형할 경우, 시간 복잡도가 O(N)까지 상승할 수 있다.https://cascade.tistory.com/97 [열혈자료구조] 11강. 탐색(Search) 1* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 11강에서 다루는 이전에 다루었던 단순 탐색, 이진 탐색을 다루는 것이 아니라, 트리 구조를cascade.tistory.com 예를 들어, 아래와 같은 트리가 "불균형한 트리"이다.이러한 트리의 모양은 5, 4, 3..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 11강에서 다루는 이전에 다루었던 단순 탐색, 이진 탐색을 다루는 것이 아니라, 트리 구조를 기반으로 하는 탐색을 다룬다. 즉, 데이터를 어떻게 저장하는지가 탐색의 효율에 큰 영향을 미칠 수 있다. 단순 탐색과 이진 탐색은 이전 포스팅을 참고!! https://cascade.tistory.com/62 탐색 알고리즘 (백준 1920번)무작위로 N개의 수가 들어있는 리스트가 있다고 하자. 이 안에 특정 수 x가 들어있는지 찾는 최적의 알고리즘은 무엇일까? 이런 류의 문제를 탐색(searching)문제라고 한다. 탐색 문제에는 크게 세cascade.tistory.com 보간 탐색(Interpolation S..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 우선순위 큐(Priority Queue)란? 우선순위 큐 또한 큐와 마찬가지로 enqueue, dequeue 연산이 있으나, 연산의 결과에서 차이를 보인다. 뒤에서 데이터를 enqueue하고 앞에서 dequeue 하는 큐와 달리, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 프로그래머가 결정한 기준에 따라 데이터에 우선순위를 매기고, 해당 순서에 따라 데이터를 꺼낼 수 있도록 하는 것이다. 우선순위 큐는 아래 세 가지 방법으로 구현한다. 배열을 기반으로 구현 연결 리스트를 기반으로 구현 힙(heap)을 기반으로 구현 배열을 기반으로 구현 배열을 기반으로 구현..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 열혈 자료구조 교재에서는 이제까지 리스트, 스택, 큐의 자료구조를 다루었다. 이들은 모두 선형적인 자료구조인 반면, 본 포스팅에서 정리할 트리는 비선형 자료구조이다. 트리는 컴퓨터 디렉토리, 가계도, 조직도, 의사결정 트리 등의 계층적 정보를 표현할 수 있는 자료구조이다. 트리 용어 노드(Node): 트리의 구성 요소, 위 그림에서는 2, 7, 5 등의 숫자에 해당 간선(Edge): 노드와 노드를 연결하는 선 루트 노드(Root node): 최상위의 노드, 위 그림에서는 2 단말 노드(Terminal node): 아래에 다른 노드가 연결되지 않은 노드, 위 그림에서는 2, 5, 11, 4 / Leaf ..