08 우선순위 큐 Priority Queue 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 우선순위 큐의 개념 1-1. 우선순위 큐란 1-2. 우선순위 큐의 기능 1-2. 우선순위 큐의 표현방법 히프 2-1. 히프란? 2-2. 배열을 이용한 구현 2-3. 히프를 통한 구현 우선순위 큐 응용 3-1. 히프 정렬 3-2. 머신 스케줄링 3-3. 허프만 코드 1. 우선순위 큐의 개념 1-1. 우선순위 큐란? 우선순위 큐(Priority Queue)는 우선순위를 가진 항목들을 저장하는 큐로 FIFO(First In First Out) 순서가 이닌 순위가 높은 데이터가 먼저나가는 자료구조를 말한다. 스택 큐, 우선순위 큐 비교 자료구조 우선 삭제되는 요소 스택 가장 최근에 들어온 데이터 ..

07 트리 Tree 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 트리의 개념 1-1. 트리란 1-2. 트리의 표현방법 트리의 종류 2-1. 이진 트리 2-2. 이진 탐색 트리 트리의 순회 3-1. 전위순회 3-2. 중위순회 3-3. 후위순회 트리의 구현 4-1. 이진 트리 구현 4-2. 이진 탐색 트리 구현 1. 트리의 개념 1-1. 트리란? 트리는 리스트, 스택, 큐와 같은 선형 자료 구조가 아닌 계층적인 특징을 가지고 있는 비선형 자료 구조이다. 트리라고 부르는 이유는 나무를 엎어놓은 것과 같은 모양새를 하고 있어 그 이름이 붙게 되었다. 트리를 이해하기 위해 필요한 용어 노드(node): 트리의 구성요소 간선(edge): 노드를 연결하는 선 루트(root): 부모가 없는 ..

06 연결리스트2 Linked List 목차 연결리스트 응용 1-1. 다항식 계산 1-2. 연결리스트 스택 1-3. 연결리스트 큐 원형 연결리스트 2-1. 원형 연결리스트란? 2-2. 원형 연결리스트 구현 이중 연결리스트 3-1. 이중 연결리스트란? 3-2. 이중 연결리스트구현 1. 연결리스트 응용 1-1. 다항식 계산 2개의 다항식을 더하는 덧셈 연산을 구현한다. 헤더노드를 통해 head부분과 tail부분을 따로 관리해 다항식 연산을 좀 더 효율적으로 할 수 있다. 코드 링크: 다항식 계산 1-2. 연결리스트 스택 링크드리스트로 스택을 구현했다. top을 이용해 스택을 관리한다. heap영역이 허용하는한 스택노드를 계속해서 생성할 수 있고, 노드를 이용한다는 점만 빼면 행렬구조체를 이용한 스택과 거의 ..

05 연결리스트 Linked List 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 1. 연결리스트의 개념 1-1. 리스트란? 리스트는 자료를 정리하는 방법 중의 하나로, 할일 목록 등과 같은 것들을 관리할 때 쓰이는 자료구조이다. 리스트는 항목이 차례대로 저장되어 있으며, 각 항목들은 순서와 위치를 가지고 있다. 1-2. 연결리스트의 기능 리스트의 기능는 삽입, 삭제, 탐색 등의 연산을 수행할 수 있고, Node를 통해 연결된다. 리스트의 ADT는 아래와 같다. - 객체: n개의 element 형으로 구성된 순서가 있는 모임 - 연산 insert(list, pos, item) ::= pos 위치에 요소를 추가한다. insert_last(list, item) ::= 맨 끝에 요소를 추..

04 큐 Queue 1. 큐의 개념 1-1. 큐란 무엇일까? 큐는 스택과 반대의 자료구조이다. 먼저 온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out)의 특성을 가지고 있다. 스택도 많이 사용하는 자료구조지만, 큐는 스택보다 많이 사용되는 자료구조로 그 쓰임새가 많다. 일상생활의 예로는 매표소, 톨게이트 등이 있다. 순서대로 줄을 서는 모양이다. 1-2. 큐의 기능 큐의 기능은 스택과 비슷하다. 데이터를 삽입하고 읽어오고 삭제한다. 다만, 큐는 [top만 가지고 있는 스택]과는 다르게 front와 rear를 가지고 있다. front는 데이터가 삭제되는 부분을 가리키고, rear는 제일 나중에 들어온 데이터를 가리킨다. 스택의 추상자료형은 아래와 같다. 객체: 0개 이상의 요소..

03 스택 Stack 1. 스택의 개념 1-1. 스택이란? 스택은 쌓아놓은 더미이다. 상자를 쌓는다고 하면 아래에서부터 차곡차곡 쌓아놓을 것이다. 중간에 있는 상자가 필요하면 맨위에서부터 상자를 하나씩 빼서 꺼낼 것이다. 이런 입출력 형태를 선입후출(FILO: First In Last Out) 또는 후입선출(LIFO: Last In First Out)이라고 한다. 함수를 호출할 때도 컴퓨터 시스템은 위와 같은 스택 구조를 사용한다. 시스템 스택에 함수를 차곡차곡 쌓아 위에서부터 차례대로 꺼내 수행한다. 1-2. 스택의 기능 가장 기본적인 스택은 6가지 기능을 가지고 있다. create(): 스택을 생성한다. is_full(s): 스택이 포화상태인지 검사한다. is_empty(s): 스택이 공백상태인지 검..