13 해싱 Hashing 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 해싱의 개념 1-1. 해싱이란 1-2. 해시테이블 Hash Table 1-3. 해싱의 구조 1-4. 해시함수 개방 주소법 Open Addressing 2-1. 선형 조사법 Linear Probing 2-2. 이차 조사법 Quadratic Probing 2-3. 이중 해싱법 Double Hashing 체이닝 Chaining 해싱의 성능 분석 1. 해싱의 개념 1-1. 해싱이란? 해싱을 한 마디로 표현하자면 복호화가 불가능한 일방향 암호이다. 해싱이란 앞에서 배웠던 반복 비교를 사용하지 않고 특정 계산만으로 자료의 저장 주소를 찾아내는 탐색 방법이다. O(1)의 시간복잡도로 값을 찾아내는 것이다. 여기서 말하는 ..
12 탐색 Search 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 탐색의 개념 1-1. 탐색이란 정렬되지 않은 배열에서의 탐색 2-1. 순차 탐색 2-2. 개선된 순차 탐색 정렬된 배열에서의 탐색 3-1. 이진 탐색 3-2. 색인 탐색 3-3. 보간 탐색 균형 이진 탐색 트리 4-1. AVL 트리 4-2. 2-3 트리 1. 탐색의 개념 1-1. 탐색이란? 탐색이란 여러 개의 자료 중에서 원하는 자료를 찾는 작업을 말한다. 컴퓨터가 가장 많이 하는 작업 중 하나이다. 그런만큼 효율성이 가장 중요한 영역이라고 볼 수 있다. 탐색의 단위는 항목이고 항목을 구별해주는 기준은 키(key)이다. 탐색키와 데이터로 이루어진 여러 개의 항목 중 원하는 탐색키를 찾는 것이 탐색이다. 배열, ..
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)..
10 그래프 - 최소 신장 트리(MST)와 최단경로 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 최소 비용 신장 트리 1-1. 신장 트리란 1-2. Kruskal의 MST 알고리즘 1-3. Prim의 MST 알고리즘 최단 경로 2-1. Dijkstra 알고리즘 2-2. Floyd-Warshall 알고리즘 위상 정렬 1. 최소 비용 신장 트리 1-1. 신장 트리란? 신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 절대 사이클이 있어서는 안 된다. n개의 정점을 가지는 그래프의 신장 트리는 n-1개의 간선을 가진다. 이미지 출처: https://imgur.com/xYkNNxl 위의 그림을 살펴보면 신장트리는 그래프의 최소 연결 부분 그래프..
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) 순서가 이닌 순위가 높은 데이터가 먼저나가는 자료구조를 말한다. 스택 큐, 우선순위 큐 비교 자료구조 우선 삭제되는 요소 스택 가장 최근에 들어온 데이터 ..
