본문 바로가기

Computer Science/자료구조15

[자료구조] 해싱 (Hashing) 해싱 (Hashing) 검색 키 값을 입력하여 특정 알고리즘(산술 연산)을 통해 검색 자료의 위치(주소)를 계산하여 알 수 있게 하는 검색 방식 예시 키 : 125 산술 연산 : 125 MOD 100 = 25 → 25가 검색 자료의 주소가 된다. 검색 시간 복잡도 : $O(1)$ 좋은 해싱 함수 조건 조건 설명 낮은 충돌 발생 빈도 충돌이 적게 발생할 수록 좋다. 높은 해시 테이블 사용률 해시 테이블을 고르게 분포시킬 수록 저장효율이 좋다. 빠른 해싱 함수 계산 해싱 함수가 계산 속도가 빠를 수록 해싱 검색에 걸리는 시간을 감소시킨다. 해싱 함수 종류 1. 나머지 함수 가장 일반적으로 사용되며 검색 키 값 K에 해시 테이블 크기 M으로 나눈 나머지를 해시 주소로 사용 예시 검색 키 값 (K) : 125 .. 2020. 11. 9.
[자료구조] 신장 트리, 최소 비용 신장 트리 신장 트리 (Spanning Tree) 신장(Spanning) : 모든 노드를 포함한다는 의미 트리의 일종이기 때문에 cycle이 없어야 한다. 기존 그래프가 가진 모든 노드를 순환 없이 서로 연결시킨 트리 트리 간선 : 신장 트리에 포함된 간선 비트리 간선: 신장 트리에 포함되지 않은 간선 ​ 최소 비용 신장 트리 (Minimum Cost Spanning Tree) 무향 가중 그래프의 신장 트리 중에서 가중치의 합이 최소인 신장 트리 최소 신장 트리 구하는 알고리즘 : Prim(프림), Kruskal(크루스칼) 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타.. 2020. 9. 15.
[자료구조] 그래프 (Graph) 그래프 (Graph) 노드(Node, Vertex), 간선 (Edge)의 집합 객체 사이의 연결 관계를 표현하는 자료구조 가장 표현력이 우수한 자료구조로, 현실세계의 다양한 문제를 효과적으로 모델링하는 목적 트리는 계층구조가 아닌 일반적인 관계는 나타낼 수 없다는 한계를 지님 ​ 그래프 종류 구분 종류 설명 간선의 방향성 무방향 그래프 방향X 방향 그래프 방향O 간선의 가중치 가중 그래프 간선에 가중치 할당 구조적 특징 완전 그래프 연결 가능한 최대 간선 수 가짐 부분 그래프 원래 그래프의 일부분 다중 그래프 중복된 간선 포함 ​ 1. 무방향 그래프 간선에 방향이 없는 그래프 노드 : V(A) = { A, B, C, D, E} 간선 : G(A) = {(A,B), (B, D), (C,D), (D,E), (.. 2020. 9. 15.
[자료구조] 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리 (Binary Search Tree) 특정 키 값에 해당하는 노드를 빠르게 찾는 것이 주된 기능 효율적인 자료 검색이 목적 조건 모든 노드는 유일한 키를 가짐(중복x) 왼쪽 서브트리 노드들 키 값 루트 노드 키 값 왼쪽, 오른쪽 서브트리 = 이진 탐색 트리 => 왼쪽 서브트리 키 중위 순회(InOrder) 방식으로 나열하면 키 값 크기대로 나열됨 ​ 1. 검색 연산 입력 값 현재 노드 값 : 오른쪽 서브트리로 이동 입력 값 = 현재 노드 값 : 검색 완료! ​ 2. 삽입 연산 입력 값 현재 노드 값 : 오른쪽 서브트리로 이동.. 2020. 9. 15.

티스토리툴바