끄적끄적 끄적끄적

참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부 날짜 : 21.04.04 검색의 이해 자료를 만들고 저장하고 정렬하는 것은 자료를 사용하기 위함이고, 사용하려면 자료 중에서도 원하는 항목을 찾아야 하는데 이것이 바로 검색(Search)이다. 저장한 자료는 그 자료를 구별하여 인식할 수 있는 키를 가지고 있는데, 이것을 탐색키(Search Key)라고 한다. 자료를 검색하는 것은 원하는 탐색키를 가진 항목을 찾는 것이다. 원하는 항목을 찾으면 검색 성공(Hit), 못 찾으면 검색 실패(Miss)라고 한다. 검색은 메모리 내에서 수행하는 내부 검색과 메모리 외부에 있는 보조 기억 장치에서 진행하는 외부 검색, 검색 대상의 키를 비교하여 검색하는 비교 검색과 계수적인 성질을 이용한 계산으로 검색하는 계산..

참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부날짜 : 21.04.03 히프 정렬 1. 히프정렬의 이해 히프 정렬은 히프 자료구조를 이용하여 정렬하는 방법이다 [자료구조]CH7. 트리(히프) 참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부 날짜 : 21.02.22 히프의 개념과 연산 및 구현 1. 히프의 개념 히프(Heap)는 완전 이진 트리에 있느 노드 중에서 키 값이 가장 큰 노드나 키 값이 가 crystal93.tistory.com 히프에서는 항상 가장 큰 원소가 루투 노드가 되고, 삭제 연산을 하면 항상 루토 노드의 원소를 삭제하여 반환하는 특징이 있다. 그러므로 최대히프에서 삭제연산을 수행하면 내림차순으로 정렬된 원소를 얻을 수 있다. * 순서 ① 초기 상태 : 정렬되지 않은 자료를 ..

참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부 날짜 : 21.03.22 삽입 정렬 1. 삽입 정렬의 이해(Insert Sort) 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식으로 정렬을 수행한다. 삽입 정렬에는 정렬된 앞부분의 원소는 부분 집합 S(Sorted Subset), 정렬되지 않은 나머지 원소는 부분 집합 U(Unsorted Subset)이 된다. U가 공집합이 되면 삽입 정렬 완성. 2. 삽입 정렬 알고리즘 크기가 n인 배열 a[]의 원소를 삽입 정렬 InsertionSort(a[] , n) for (i ← 1 ; i < n ; i ← i+1) do { //초기에 인덱스 0은 부분집합 S에 해당하므로 인덱스 1부터 시작 temp ← a[i]; j ← i; if..

참조: C로 배우는 쉬운 자료구조(이지영 저) 공부 날짜 : 21.03.17 정렬의 이해 1. 정렬의 개념 정렬(sort)이란 순서 없이 배열된 자료를 작은 것부터 큰 것 순서인 오름차순(Ascending)이나 큰 것부터 작은 것 순서인 내림차순(Descending)으로 재배열하는 것이다. 자료를 정렬하는 데 사용하는 기준이 되는 특정값을 키라고 한다. 2. 정렬 방식의 분류 1) 내부 정렬 : 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식 속도는 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한된다. 구분 종류 비고 비교식 교환방식 선택 정렬, 버블 정렬, 퀵 정렬 삽입방식 삽입 정렬, 셀 정렬 병합방식 2-way 병합, n-way 병합 선택방식 (이진트리를 사용)히프 정렬, 트..

참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부 날짜 : 21.03.13 신장 트리와 최소 비용 신장 트리 1. 신장 트리 모든 정점이 n개인 무방향 그래프에서 정점이 n개이고 간선이 n-1개인 사이클이 없는, 트리 형태의 부분 그래프를 신장 트리(Spanning Tree)라고 한다. 즉, 간선을 최소로 이용하여 모든 정점을 연결한 그래프이다. 깊이 우선 탐색을 이용하여 생성된 신장 트리를 깊이 우선 신장 트리, 너비 우선 탐색을 이용하여 생성된 신장 트리는 너비 우선 신장 트리라고 한다. 2. 최소 비용 신장 트리 가중치 그래프에서는 간선에 가중치가 주어진다. 무방향 가중치 그래프에서 신장 트리 비용은 신장 트리를 구성하는 간선 n-1개의 가중치를 합한 값이 된다. 이때 가중치 합이 최소인 신장 ..

참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부 날짜 : 21.03.10 그래프의 구조 1. 그래프의 개념 그래프는 m:n 관계를 표현하는 비선형 자료구조이다. 객체를 나타내는 정점(Vertex)와 객체를 연결하는 간선(Edge)의 집합으로 구성된다. G=(V,E) 2. 그래프의 종류 1) 무방향 그래프 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 정점 Vi과 Vj를 연결하는 간선을 (Vi,Vj)라고 표현하고, (Vi,Vj)와 (Vj,Vi)는 같은 간선을 나타낸다. 그래프는 정점의 집합 V(G), 간선의 집합 E(G)를 사용해서 나타낼 수 있다. 2) 방향 그래프 간선에 방향이 있는 그래프로 다이그래프라고도 한다. 정점 Vi에서 Vj를 연결하는 간선을 로 표현한다. 이때 Vi가 꼬리(Tail..

참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부 날짜 : 21.02.22 히프의 개념과 연산 및 구현 1. 히프의 개념 히프(Heap)는 완전 이진 트리에 있느 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기위해 만든 자료구조이다. 키값이 가장 큰 노드를 찾기 위한 히프가 최대 히프, 키값이 가장 작은 노드를 찾기 위한 히프가 최소 히프이다. 최대 히프는 {부모 노드의 키값>=자식 노드의 키값} 의 관계를 가지는 노드들의 완전 이진 트리이고, 최소 히프는 {부모 노드의 키값

참조 : C로 배우는 쉬운 자료구조 (이지영 저) 공부날짜 : 21.02.20 균형 이진 탐색 트리 1. 균형 이진 탐색 트리의 개념 높이에 대한 균형 조건을 추가하여 정의한 트리를 균형 이진 탐색 트리 또는 균형 트리라고 한다. 대표적인 예가 AVL트리이다. 2. AVL트리의 개념과 유형 각 노드에서 왼쪽 서브 트리의 높이 hL과 오른쪽 서브 트리의 높이 hR의 차이가 1이하인 트리이다. * 왼쪽 서브 트리 < 부모 노드 < 오른쪽 서브 트리의 크기 관계 * 각 노드의 서브 트리의 높이의 차이(hL-hR)를 노드의 균형 인수(Balance Factor)라 한다. * 각 노드의 균형 인수는 {-1,0,1}의 값만 가지게 하여 균형을 유지한다. 균형인수가 양수(+)이면 왼쪽 서브 트리에, 음수(-)이면 오..