🔧소프트웨어 개발자주
탐색과 해싱
이진 탐색은 정렬되어 있어야 한다. 해싱은 충돌을 어떻게 다루느냐가 핵심.
순차 탐색은 O(n), 이진 탐색은 O(log n)이지만 자료가 정렬되어 있어야 한다.
해싱 함수: 제산법(나머지), 중간 제곱법, 폴딩법, 기수 변환법, 숫자 분석법.
서로 다른 키가 같은 자리로 가는 것이 충돌이다. 해결 방법은 개방 주소법(선형 조사·이차 조사·이중 해싱)과 체이닝(연결 리스트로 매달기)이다.
시험에는 이렇게
해싱 함수 이름과 충돌 해결 방법을 짝짓게 한다.
실기에도 나오는 개념입니다. 실기는 고르는 것이 아니라 적으므로 용어를 글자 그대로 외워 두세요.
확인 문제
이 개념은 실기에도 3문항 나옵니다. 고르는 것과 적는 것은 다르니 실기 탭에서 손으로도 한 번 적어 보세요.