자료구조

이진검색트리(BST) 정의 1. 이진 탐색(binary search)와 연결 리스트(Linked list)를 결합한 자료구조이다. * 이진 탐색: 탐색 범위를 두 부분으로 분할 하면서 찾는 자료구조, 삽입 및 삭제는 불가능, 보통 배열로 구성 2. 이진 탐색의 효율적인 탐색능력을 유지하면서, 자료 삽입(Insert)과 삭제(Delete)를 가능하게끔 고안되었다. 이진검색트리 특징 1. 트리의 모양은 상관 없으며 이진트리여야 한다. 2. 부모노드의 값을 중심으로 왼쪽 자식 트리의 값은 작고, 오른쪽 자식 트리의 값은 커야한다. 3. 중복된 노드는 없어야 한다. 4. 이진 탐색트리는 중위 순회를 통해 순회를 진행한다. -> 이진 검색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다. 중위 순회 결과..

힙(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. 정점: 간선이 연결되는 ..

Stack(스택) 1. LIFO(후입선출) - 가장 나중에 들어온 값이 가장 먼저 나오는 구조 2. 스택이 사용되는 곳 가. 함수의 콜 스택 나. 연산자 후위 표기법 다. 시스템 스택 라. 뒤로가기 버튼 3. 스택이 가지고 있는 함수 가. push(): 데이터를 넣는다. 나. pop(): 데이터를 꺼낸다. 다. isEmpty(): 스택이 비어있는지 확인한다. 라. isFull(): 스택이 꽉 차있는지 확인한다. 4. 스택포인터 가. push(), pop()을 할 때 해당 위치를 알고 있어야 하므로, 해당위치를 기억하고 있는 포인터 나. 스택 포인터의 초기화 값은 -1 Queue(큐) 1. FIFO(선입 선출) - 가장 먼저 들어온 값이 가장 먼저 나오는 구조 2. 큐가 사용되는 곳 가. 이벤트 큐 나. ..