← 회차 전체 문제

공개 기출자동 검사 완료2021년 국가직 기출 · 컴퓨터일반 · 자료구조·알고리즘 · 13번

해쉬(Hash)에 대한 설명으로 옳지 않은 것은?

1
연결리스트는 체이닝(Chaining) 구현에 적합하다.
오답 이유체이닝은 같은 버킷으로 해시된 원소들을 연결 리스트 등에 이어 저장하는 충돌 해결법이다.
2
충돌이 전혀 없다면 해쉬 탐색의 시간 복잡도는 O(1)이다.
오답 이유충돌 없이 주소가 바로 계산되면 평균 탐색은 한 번의 버킷 접근인 O(1)이다.
3
최악의 경우에도 이진 탐색보다 빠른 성능을 보인다.
정답 근거모든 키가 같은 버킷에 몰리면 체이닝 탐색은 O(n)이 될 수 있어 O(log n) 이진 탐색보다 항상 빠르지 않다.
4
해쉬 함수는 임의의 길이의 데이터를 입력받을 수 있다.
오답 이유해시 함수는 임의 길이 키를 정해진 범위의 해시값이나 테이블 주소로 매핑할 수 있다.

정답·상세해설

정답 3번

해시 탐색은 충돌이 적으면 평균 O(1)이지만, 모든 키가 한 버킷에 몰리는 최악의 경우 O(N)까지 느려질 수 있습니다. 정렬된 자료의 이진 탐색은 O(log N)이므로 최악 상황에서는 이진 탐색이 더 빠릅니다. 따라서 ③의 설명이 옳지 않습니다.

콘텐츠 기록

콘텐츠 정보

자료 유형: 공개 기출
검수 상태: 자동 검사 완료
해설 작성·검수: 정처LAB 자동 검사
최종 검수: 자동 검사 완료

이 번호부터 전체 회차 풀기 내 오답 복습 회차 전체보기 시험별 CBT 안내