자료 구조

8장 해시 테이블로 매우 빠른 룩업

✍🏻 누자알 앞부분은 기본 내용이고, 다시 공부할 필요가 없다고 생각했다. 그래서 정리에 조금 소홀함이 있었다. 그러나 최근 쳤던 코딩 테스트에서 CS 지식 중 선택 정렬과 버블 정렬에 대해 물어보는 문제가 나왔다. 와! 마침 누자알 4장과 5장이 버블 정렬과 선택 정렬에 대해 자세하게 설명하고 있어서 해당 문제를 맞출 수 있었다. 역시 공부는 기본이 중요하다는 것을 다시 깨달았다. 기록하지 않으면 까먹을 것 같아서 느슨해지지 말자는 다짐으로 여기 기록한다. 배열이 정렬되어 있지 않다면 컴퓨터는 선형 검색을 해야 하므로 특정 값이 배열 내에 존재하는지 검색하기 위해 O(N)의 수행 단계가 필요하다. 정렬된 배열이라면 컴퓨터가 이진 검색을 수행할 수 있으므로 O(log N)의 수행 단계가 필요하다. 그러나..