[알고리즘] 사전ADT(1) - 설명

사전ADT는 (키, 원소) 쌍으로 표현된 데이터 항목의 모음을 추상데이터구조로 모델링한 것이다.

사전ADT에는 2종류가 있다.

- 무순사전ADT : 데이터항목이 키 순서와 관계 없이 저장된 사전(Ex. 기록파일(log file))

- 순서사전ADT : 키 순서에 의해 정렬이 되어 저장된 사전(Ex. 일람표)

사전ADT메소드

1) 일반메소드

 - integer size() : 사전의 항목 수를 반환

 - boolean isEmpty() : 사전의 비어 있는지 여부를 반환

2) 접근메소드

- element findElement(k) : (키, 원소) 항목들의 모음인 사전에 키 k를 가진 항목이 존재하면 해당 원소를 반환, 그렇지 않으면 특별원소 NoSuchKey를 반환

3) 갱신메소드

- insertItem(k, e) : 사전에 (k, e) 항목을 삽입

- element removeElement(k) : 사전에 키 k를 가진 항목이 존재하면 해당 항목을 삭제하고 원소를 반환, 그렇지 않으면 특별 원소 NoSuchKey를 반환

사전을 구현하는 가장 중요한 목적은 탐색이다.

사전의 작업에 영향을 미치는 두가지의 전제가 있는데, 바로 유일키와 중복키이다.

유일키는 원소가 유일하게 존재하는 경우이다

Ex) (키1, 원소1) (키2, 원소4) (키3, 원소3) (키4, 원소2)

중복키는 원소가 중복하게 존재하는 경우이다.

Ex) (키1, 원소1) (키2, 원소1) (키3, 원소2) (키4, 원소1)

리스트로 구현된 사전의 성능

	insertItem	findElement	removeElement
무순사전	O(1)	O(n)	O(n)
순서사전	O(n)	O(log n) - 이진탐색이용	O(n)

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사