![]()
이진검색트리(BST) 정의 1. 이진 탐색(binary search)와 연결 리스트(Linked list)를 결합한 자료구조이다. * 이진 탐색: 탐색 범위를 두 부분으로 분할 하면서 찾는 자료구조, 삽입 및 삭제는 불가능, 보통 배열로 구성 2. 이진 탐색의 효율적인 탐색능력을 유지하면서, 자료 삽입(Insert)과 삭제(Delete)를 가능하게끔 고안되었다. 이진검색트리 특징 1. 트리의 모양은 상관 없으며 이진트리여야 한다. 2. 부모노드의 값을 중심으로 왼쪽 자식 트리의 값은 작고, 오른쪽 자식 트리의 값은 커야한다. 3. 중복된 노드는 없어야 한다. 4. 이진 탐색트리는 중위 순회를 통해 순회를 진행한다. -> 이진 검색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다. 중위 순회 결과..
![]()
목차 1. 선택정렬 2. 거품정렬 3. 삽입정렬 4. 퀵 정렬 5. 병합 정렬 6. 힙 정렬 안정 정렬과 불안정 정렬 1. 안정 정렬: 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ex) caBb -> aBbc (여기서 B==b 같은 값이다.) 2. 불안정 정렬: 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 ex) caBb -> abBc (여기서 B==b 같은 값이다.) 선택정렬 - 불안정 정렬 1. 특징 가. 버블 정렬과 유사한 알고리즘이다 나. 해당 자리를 선택하고 그 자리에 오는 값을 찾는 알고리즘이다. 1) 주어진 배열 중에 최소값을 찾는다. 2) 그 값을 맨 앞에 위치한 값과 교체한다. 3) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 다. 구현이 매우 간단하며..
![]()
힙(Heap) 특징 1. 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 2. 여러개의 값들 중에서 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료구조이다. 3. 힙은 반 정렬 상태를 유지한다. 4. 힙 트리는 중복 값을 허용한다. 우선순위 큐 1. 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나가는 구조 2. CPU 작업 스케쥴링, 시뮬레이션 시스템에서 사용 3. 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능한데, 힙으로 구현하는게 가장 효율적. 힙 종류 1. 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 2. 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 힙 구현 특징 1. 힙을..
![]()
그래프: 하나 이상의 정점(혹은 노드)을 포함하는 집합 정점(v)와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E를 가진다. 정점간의 관계를 표현하는 자료구조이다. 등장 배경 - 수학자 오일러가 쾨니히스베르크 다리 문제를 해결하기 위해 그래프를 고안 * 쾨니히스베르크 다리 문제: 모든 다리를 단 한 번씩 지나 다시 출발점으로 되돌아 올 수 있는가? - 육지를 점으로 다리를 선으로 표현하여 문제를 추상화함 - 육지의 건물이나 다리 같은 불필요한 요소는 다 버리고 육지와 다리의 '관계'만을 점과 선으로 나타낸 것이 그래프의 시초 그래프 표기법 G = (V, E) 1. G: 그래프(Graph) 2. V: 노드 또는 정점(Vertex) 3. E: 간선(Edge) 그래프의 용어 1. 정점: 간선이 연결되는 ..
