11 정렬 Sort 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 정렬의 개념 1-1. 정렬이란 1-2. 정렬의 분류 정렬의 종류 2-1. 선택 정렬 2-2. 삽입 정렬 2-3. 버블 정렬 2-4. 셸 정렬 2-5. 합병 정렬 2-6. 퀵 정렬 2-7. 기수 정렬 정렬 알고리즘의 비교 1. 정렬의 개념 1-1. 정렬이란? 정렬이란 데이터나 물건을 크기를 기준으로 오름차순이나 내림차순으로 나열하는 것을 의미한다. 정렬은 컴퓨터 공학을 포함한 모든 과학기술 분야에서 가장 기본적이고 중요한 알고리즘이다. 정렬은 특히 자료 탐색에 가장 핵심이 된다. 만약 사전이 알파벳으로 정렬되어있지 않다면 특정 단어를 찾는 것은 굉장히 어려운 일이 될 것이다. 정렬시켜야할 대상을 레코드(record)..
09 그래프 Graph 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 그래프의 개념 1-1. 그래프란 1-2. 그래프의 종류 1-3. 네트워크 1-4. 그래프 용어 그래프의 표현방법 2-1. 인접행렬 방식 2-2. 인접리스트 방식 그래프의 탐색 3-1. 깊이 우선 탐색 DFS 3-2. 너비 우선 탐색 BFS 1. 그래프의 개념 1-1. 그래프란? 그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료구조이다. 그래프의 예로는 지도에서 도시들의 연결상태, 전기회로의 소자 간 연결 상태, 도로망, 대학교 선수과목 관계 등이 있다. 트리도 일종의 그래프로 받아들여진다. 선형리스트, 트리로는 도시, 소자, 자원, 프로젝트 등의 객체들이 서로 연결되어 있는 복잡한 구조를 표현..
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영역이 허용하는한 스택노드를 계속해서 생성할 수 있고, 노드를 이용한다는 점만 빼면 행렬구조체를 이용한 스택과 거의 ..
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): 스택이 공백상태인지 검..
