기록하는 습관 "기습"

해시테이블 지금까지 트리 자료구조는 대부분은 다른 원소와 비교하여 저장할 위치를 찾아갔다. 그러나 해시테이블은, 원소를 저장할 위치가 그 원소 값에 의해 결정되는 자료구조다. 해시테이블의 특징은 다음과 같다. 저장/검색/삭제에 있어서 상수에 가까운 수행시간을 갖는다. = > Θ(1) 최소 원소 찾기 같은 연산은 지원하지 않는다. 지금부터 위의 그림을 예시로 해시테이블에 대해 설명하겠다. 위와 같은 해시테이블의 크기 m을 7이라 하자. 그렇다면 테이블은 0~6까지의 인덱스를 갖는다. 해시함수 Hash function 원소를 저장할 때, 가운데 해시함수 hash function를 거쳐서 적절한 위치에 저장된다. 따라서 해시함수는 검색 키 값을 해시 테이블주소로 매핑하는 함수라는 의미다. 해시함수는 입력원소가..

검색 search이란 컴퓨터에 저장한 자료 중에서 원하는 정보를 찾는 작업이다. 다르게 말하자면, 원하는 검색키를 지닌 항목을 찾는 것이며, 원하는 항목이 있을 경우엔 '검색 성공', 없을 경우엔 '검색 실패'가 된다. 원소의 삽입 삭제를 위해서도 검색 연산을 수행하기도 한다. 검색 알고리즘을 고를 땐 고려해야 할 사항이 있다. 수행 시간 복잡도, 자료구조, 정렬 여부, 자료의 위치 등이 있다. 검색 수행 위치에 따라, 메모리에서 수행하면 내부 검색, 보조기억장치에서 수행하면 외부 검색으로 나뉜다. 검색 방식에도 분류가 있다. 검색 대상의 키를 저장된 자료의 키와 비교하여 검색하는 '비교 검색'과 계수적인 성질 값을 이용한 계산으로 검색하는 '계산 검색'이 있다. 순차 검색 Sequential searc..