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

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

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 큐(queue)는 말 그대로 대기열이다. 놀이기구 줄을 설 때, 나중에 온 사람이 먼저 탑승하면 그건 새치기가 된다. 따라서, 대기열은 먼저 온 사람이 먼저 탑승하고, 나중에 온 사람은 나중에 탑승하는 선입선출(FIFO, First in First Out) 구조이다. LIFO 구조였던 스택과는 대비된다. 큐의 ADT 스택에는 push, pop, peek의 기능이 핵심적이었다. 큐는 데이터를 넣는 부분과 빼는 부분의 위치가 다르기 때문에, 아래와 같은 두 개의 연산이 핵심적이다. enqueue: 큐에 데이터를 넣음 dequeue: 큐에서 데이터를 뺌 이를 이용하여, ADT에 아래 5가지를 구현하자. 1...

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 드디어 길고 길었던 연결 리스트가 무려 6개의 포스팅 만에 끝났다!! 이제 6강인 스택에 대해 다뤄 보자. 스택은 지난 번 코딩 연습 때 백준에서 다룬 바 있다. https://cascade.tistory.com/61 스택(stack)구조란? (백준 9012번, 10828번) 스택 구조란, 쌓여 있는(stack) 더미처럼 된 자료구조를 말한다. 그림처럼 쌓은 수건을 위에서부터 사용하면서, 빨래한 새 수건을 다시 위에 쌓으면 아래 있는 수건은 계속 안 써서 먼지가 쌓인다. cascade.tistory.com 스택의 정의는 지난 번 포스팅을 참고하도록. LIFO 구조라는 건 기억하고 가고, 어떤 기능을 구..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 드디어!!!!! 길고 길었던 연결 리스트 마지막 포스팅이다. 그동안 3개의 챕터에 걸쳐 연결 리스트에 관해 공부했고, 아래와 같은 내용을 공부했었다. 오늘 포스팅에서는 연결 리스트의 마지막 내용인 양방향 연결 리스트에 관해 다룰 예정이다. 3강 ADT와 배열 리스트 4강 단순 연결 리스트 5강 원형 연결 리스트, 양방향 연결 리스트 단순 연결 리스트나 원형 연결 리스트는 노드가 한쪽으로만 연결되어 있지만, 양방향 연결 리스트는 노드가 양쪽으로 연결되어 있다는 것이 차이점이다. 즉, 노드의 구조체 형태가 기존과 달리 아래와 같이 구성된다. typedef struct _node{ Data data; str..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 리스트 그림그리기 힘들군요 앞서 4강에서 구현한 단순 연결 리스트를 변형하여 원형 연결 리스트를 제작하자. 원형 연결 리스트는 단순 연결 리스트에서 머리에서 가장 먼 노드가 NULL을 가리키는 것이 아니라, 머리에서 가장 가까운 노드를 가리키도록 하여 원형 구조를 이루는 것을 말한다. 새로운 노드 1을 머리에 추가한다고 한다면 아래와 같이 변한다. 새로운 노드 1을 꼬리에 추가한다고 하면 아래와 같이 변한다. 이때, 마지막 노드를 가리키는 포인터 변수는 tail이고, 첫 노드를 가리키는 포인터 변수는 tail->next가 된다. 이렇게 원형으로 연결 리스트를 구현하는 것의 특징은, LNext 함수의 무..