<Algorithm> 검색구조 ① 연결리스트와 이진검색

본 게시물은 영남대학교 조행래 교수님의 강의를 기반으로 작성되었습니다.

1. Symbol Table이란?
   • (Key,Value)의 모임이며, 특정 키와 그 키에 해당되는 값의 쌍을 삽입
   • 키가 주어질 때, 관련된 값을 검색

2. 연결리스트를 이용한 순차검색
   • (Key,Value) 쌍으로 구성된 연결 리스트를 유지
     • 검색 : 모든 키를 스캔하면서 입력 키와 일치 여부 확인
     • 삽입 : 모든 키를 스캔하면서 입력 키와 일치 여부 확인하고 일차하는 키가 없으면 리스트의 제일 앞에 (Key,Value) 쌍을 삽입
   • 하나하나씩 전부 비교를 해야해서 시간이 굉장히 오래걸림

3. 정렬된 배열을 이용한 이진검색
   • 아래 알고리즘은 keys와 vals를 따로 두개의 배열을 사용하여 정렬
   • 원소를 put할 경우, binary-search를 통해 put할 자리를 먼저 찾고, 그 자리 이후의 원소들은 마지막원소부터 오른쪽으로 한칸씩 밀어 공간을 확보한 다음 index에 put을 한다.
   • 당연히 순차검색보다는 시간이 덜 소요되지만, put에서 한칸씩 미는 작업이 시간 복잡도를 증가시킴