본문 바로가기

CS study/[core] 데이터 구조

 (14)
17. Hash Hash 해시(Hash) 란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 과정을 말한다. 즉 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑해주는 함수이다. 키(key): 매핑전 원래 데이터의 값 해시값(Hash Value): 매핑 후 데이터의 값, 해시코드, 해시섬, 체크섬 등이라고도 한다. 해싱(Hashing) : 해시함수를 사용하여 주어진 값을 변환한 뒤, 해시 테이블에 저장하고 검색하는 기법 해시 테이블 키(key)와 값(value)이 하나의 쌍을 이루는 데이터 구조이다. 키를 해시 함수(hash function) 로 계산하여 그 값을 배열의 인덱스로 사용한다. 즉, key 값을 해시 함수를 통해서 배열의 인덱스로 바꿔주고, 그 자리에 데이터를 저장한다. 정리하면 다음과..
16. 그래프 탐색 (2) - DFS DFS (Depth-First Search) 개요 설계 모델 BFS와 같이 색깔로 정점의 상태를 구별해 보자. White: discover되지 않은 상태 즉, 처음에 모든 정점은 white 상태이다. Gray: discover는 되었지만 정점에 대해서 탐색이 끝나지 않은 상태 = Gray 정점의 인접 정점들 중 최소 한개는 white 정점인 상태 Black: discover되고 해당 정점에 대해 모든 탐색이 끝난 상태 = Black 정점의 인접 정점들은 모두 Gray 혹은 Black 상태일 것이다. DFS에서 Gray 정점은 약간 BFS와 다른데, 각 Gray 정점에서 2개의 타임스탬프를 가진다. d[v]: 정점 v의 discovery time f[v]: 정점 v의 finish time (방문할 수 있는..
15. 그래프 탐색 (1) - BFS 그래프 탐색 그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 그래프 탐색은 크게 두가지 방법이 있다. BFS (Breadth-First Search, 너비우선탐색) 개요 한 시작 정점을 정해서 인접한 정점부터 모두 탐색하는 방식이다. 설계 모델 정의 Discover: 정점을 처음 방문한다. Explore: 간선을 처음 이용한다. 정점의 구분 White: discover되지 않은 상태 즉, 처음에 모든 정점은 white 상태이다. Gray: discover는 되었지만 정점에 대해서 Explore가 끝나지 않은 상태 = Gray 정점의 인접 정점들 중 최소 한개는 white 정점인 상태 Black: discover되고 해당 정점에 대해 모든 Explore가 끝난 상태 ..
14. Graph Basics Graph 그래프란? 정점(V, vertex)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조 = 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 용어 정점(Vertex, V): 꼭짓점 (node라고도 부름) ex) 위 그래프에서 정점은 총 7개 0,1,2,3,4,5,6 이 있다. 간선(Edge, E): 꼭짓점 간의 관계, 꼭짓점을 연결하는 선 (link, branch라고도 부름) ex) 위 그래프에선 간선이 총 6개 [(0-1) ,(1-2), (1-3), (2-5), (2-6), (3-4)] 있다. 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점 ex) 위 그래프에선 정점 1의 인접 정점은 정점 0, 2, 3이 있다. 정점의 차수(degree)..
11. AVL tree AVL tree 모든 BST 연산은 $ O(d) $ (d는 트리의 높이) 이다. $ d = \lfloor \log_2 N \rfloor $ (N은 트리의 총 노드 갯수) best case: $ O(\log N) $ worst case: $ O(N) $ 여기서 차이가 나는 이유는 트리의 균형의 문제이다. BST의 균형을 맞추기 위해 고안된 알고리즘이 많다. AVL tree: Adelson-Velskii and Landis (AVL) trees (height-balanced trees) Weight-balanced trees Red-black trees Splay trees and other self-adjusting trees B-trees and other (e.g. 2-4 trees) multiway ..
10. Heapsort Heapsort 전략 i. Heapify: N개의 정렬되지 않은 array를 max Heap 구조로 만들기 ii. maximum 키를 순차적으로 pop 내림차순 정렬을 위해서는 최대힙, 오름차순 정렬을 위해서는 최소 힙을 만들면 된다. 동작 i) Heapify Bottom-up method로 최대 힙을 만들자. 이 경우 마지막 Internal node 3-node heap에서 시작한다. 이미 T가 루트인 3-node heap은 heap 구조를 만족하므로 패스 ii. 순차적으로 maximum key를 지운다. 한 번에 하나씩 최대값을 제거합니다. null을 제거하는 대신 배열에 그대로 두십시오. 이런식으로 쭉쭉 하다보면 이렇게 정렬이 된다. // 실행 과정 Enter a word to sort: SORTE..
9. Heap, Priority Queue Heap 힙은 완전 이진 트리의 일종으로 priority queue를 구현하기 위해 만들어진 자료구조 특징 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 반정렬 상태(느슨한 정렬 상태) 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) Priority Queue 우선 순위가 있는 큐, 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. Ex) 은행에서 줄을 설 때 먼저 온 순서대로(FIFO) 서비스를 받을 수 있습니다. 하지만 노인이나 장애인이 줄을서는 경우 그들에게 우선권을 부..
8. Binary Search Tree Binary Search Tree 정의: binary tree in symmetric order Binary Tree: 노드로 구성되며, 각 노드는 최대 두 개의 자식(왼쪽과 오른쪽 자식)을 가진다. Symmetric Order 모든 노드는 키를 갖는다. 모든 노드의 키는 왼쪽 하위 트리의 모든 키보다 큼 오른쪽 하위 트리의 모든 키보다 작음 중복된 노드가 없어야 한다. 이 트리에서 키 값이 가장 작은 노드 키 값이 가장 큰 노드 왼쪽 서브트리에서 가장 큰 키 값의 노드 오른쪽 서브트리에서 가장 작은 키 값의 노드 를 구하는 방법을 알아보자. 구조 Node structure Key: Value: Left: Right: BST node structure typedef int Key; typedef char..

티스토리툴바