목록자료구조 (2)
이모저모
Hash해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 의미기존의 자료 구조들은 탐색이나 삽입이 O(N)의 걸리는 반해 해시는 O(1)의 시간이 걸린다.대신 순차탐색, 구간탐색이 힘들다. Bucket해시테이블에서 하나의 원소를 의미 Slot각 버킷에 s개의 slot으로 구성충돌 대비용 Hash TableDirect Addressing Tablekey-value쌍의 데이터를 배열에 저장할 때, key값을 직접적으로 배열의 인덱스로 사용하는 방법키는 중복되지않는다고 가정하면 탐색, 저장, 삭제, 갱신 모두 O(1)로 매우 빠르다.하지만 key의 크기만큼 배열이 할당 되기 때문에 낭비되는 공간이 많아 공간적으로는 매우 비효율적이다.키가 중복되는 경우에는 리스트의 chain처럼 사용하..
DisJointSet 자료구조Union-Find set이라고 부르기도 한다.크루스칼 알고리즘에 활용하는데 사용하는 자료구조이다.물론 집합의 연산에서도 충분히 활용할 수 있다.find, union 연산만 하는 경우 위 자료구조를 활용할 수 있다.먼저 소스코드를 보자. struct DisjointSet{int component;vector parent;DisjointSet(int n):component(n),parent(n+1){fill(parent.begin(),parent.end(),-1);}int find(int v){if(parent[v]==-1) return v;return parent[v]=find(parent[v]);}bool merge(int u, int v){int pu=find(u), pv..