MintPsycho's Blog

Hash : Hash Table에 존재하는 해시함수의 결과물이다. 저장소에서 value와 매칭되어 저장된다. Hash Table : key 와 value 가 한 쌍 으로 존재하는 자료형. (연관배열 구조) 키(key), 해시함수(hash function), 해시(hash), 저장소(buckets), 값(value)로 이루어져 있다. 파이썬의 dictionary. 키 값이 배열의 인덱스로 변환되기 때문에, 검색과 저장의 평균 시간복잡도가 O(1)에 수렴한다.

자료구조 Q. (Python)Dictionary 의 정렬, 정렬이 가능한지 Q. Stack / Queue / Heap / Tree / Graph 개념 Q. Minimum Stack, Queue : O(1) 시간복잡도로 최솟값을 반환하는 함수를 구현하라. Q. 배열 하나로 스택 3개를 어떻게 구현할 지 설명하라. Q. B tree / B+ Tree Q. Binary Search Tree / Binary Heap Q. Binary Tree 의 종류 Q. Spanning Tree / Minimum Spanning Tree Q. Hash 란? Hash Table 이란? Q. Hash 충돌과 이를 회피하기위한 기법 정렬 Q. 위상 정렬이란? Q. 힙 정렬이란? Q. 대부분의 요소가 정렬되어있을때, 사용하기 적합한..

Spanning Tree란, 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프 이다. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 특징 : DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. (사이클 포함x, 모든 정점 방문o) 탐색 도중에 사용된 간선만 모으면 만들 수 있다. (n-1개의 간선으로 형성) 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Minimum Spanning Tree란, 위에서 정의한 Spanning Tree 중에서 사용된 간선들의 가중치 ..