홍시홍의 프로그래밍

해싱이란 해시 테이블을 이용한 탐색 기법 이론적으로 O(1)에 탐색가능 해시 함수 : 인덱스를 해시 주소로 바꿔주는 함수 해시 함수 조건 - 충돌이 적어야 한다 - 해시 주소가 고르게 분포되어야한다 - 계산이 빨라야 한다. 제산 함수 일 경우 소수로 나눈다 폴딩 이동 폴딩, 경계 폴딩 탐색키가 문자열일 경우 호너의 방법 사용 해싱은 충돌을 잘 처리해야 한다 충돌이 일어날 경우, 선형 조사법과 체이닝으로 해결 충돌 해결법 2가지 1. 오픈 어드레싱 2. 체이닝 오픈 어드레싱 종류 3가지 1. 선형 조사법 - h(k)+1 ,,,, +2 ,,,,+3 으로 2. 이중 조사법 - 제곱을 더함 h(k) +1^2,2^2,3^2식으로 3. 이중 해싱법 - 해시 2개 사용 - 첫번째 해시 kmod H 두번째 해시 P -..

1. 정의 컴퓨터 과학 분야 에서 서로소 집합(disjoint-set) 자료 구조, 또는 합집합-찾기(union–find) 자료 구조, 병합-찾기 집합(merge–find set)은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. 출처 : 위키피디아 내 해석 : 묶음으로 되어있지 않은 집합을 찾아내는 것, 사이클이 없음 한 노드의 부모를 찾거나 두 노드가 한 집합이 되도록 합치거나. 2. 구현 1) find(x) : x의 부모를 찾는 함수 - 경로 압축 : 시간 복잡도 상수 복잡도를 가진다고 함. 2) Union(a,b) : a와 b를 연결하는 함수(한 쪽으로 연결시켜줌) - 한 쪽으로 연결 시켜주는것이 헷갈리지 않음 ( 작은 쪽 or 큰 쪽) 3. 시간 복잡도 ..