데이터6 [Algorithms] 해쉬 테이블(Hash Table) 해시 테이블은 궁극의 탐색 알고리즘이라고 불린다. 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해싱(hashing)하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것이 기본적인 컨셉이다. 해시 테이블은 한마디로 공간을 팔아 성능을 얻어내는 것이다. 해시값으로의 접근은 다음과 같은 방식으로 이루어진다. Table[3819] = 123817; 데이터는 해시 함수를 거치면 다음 그림처럼 테이블 내의 주소(즉, 인덱스)로 변환된다. 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다. 그렇지 않으면, collision 현상이 발생한다. 통계적으로 해시 테이블의 공간 사용률이 70%~80%에 이르면 성능 저하가 나타나기 시작한다. 다른 배열 형식의.. 2017. 4. 21. Top down Approach 하향식(Top-Down) 방식은 노드가 ✔ ↓ 의 방향으로 먼저 간 다음, ✔ → 의 방향으로 채워진다. 이 두 순서로 노드가 채워지게 된다. 즉 위에서부터 채워나가되, 각 레벨에서의 삽입은 왼쪽에서 오른쪽 순서로 하게 된다. 이러기 위해선 두 가지 조건이 필요하다. 1. 각 노드에 저장된 값이 두 자식 노드에 저장된 값보다 크거나 같아야 한다. 작거나 같다는 조건으로 바꿔도 된다. 크기가 자식 노드보다 크거나 같은 경우를 Max heap이라 하고, 작거나 같은 경우를 Min heap이라고 한다. 2. 트리는 완전 균형 상태여야 하고, 마지막 레벨에 있는 leaf 노드들은 모두 트리의 가장 왼쪽 부분부터 채워져야 한다. 따라서 트리의 높이는 O(log n)이 된다. 이 두 조건은 자료구조 '힙'의 성질이.. 2017. 4. 20. 이전 1 2 다음
