사전(Dictionary)

📢   정의

• 사전은 탐색 가능한 형태의 (키,원소)쌍 항목들의 모음을 모델링 한 것이다.

• 사전에 관한 주요 작업
  1. 탐색(Searching)
  2. 삽입(Inserting)
  3. 삭제(Deleting)

• 사전에는 두 종류의 사전 존재한다.
  1. 무순사전 ADT  (Ex. "가계부")  👉  "순서가 없다"
  2. 순서사전 ADT  (Ex. "출석부", "백과사전")  👉  "학번 or 자음순,모음순" 등의 정렬된 순서가 있다.

• 사전 응용에는 두 가지
  1. 직접 응용  👉  "연락처 목록", "신용카드 사용승인", "인터넷주소 매핑"
  2. 간접 응용  👉  "알고리즘 수행을 위한 보조 데이터구조", "다른 데이터구조를 구성하는 요소"

 

📢   탐색

• 비공식적 : 탐색(Search)은 데이터 집단으로부터 특정한 정보를 추출함을 말한다.

• 공식적 : 탐색(Search)은 사전으로 구현된 데이터 집단으로부터 지정된 키(key)와 연관된 데이터 원소를 반환함을 말한다.

• 사전 구현에 따른 탐색 기법
  

구현 형태	구현 종류	예	주요 탐색 기법
리스트	무순사전 ADT	기록(log)파일	선형탐색
	순서사전 ADT	일람표	이진탐색
트리	탐새트리	이진탐색트리 AVL 트리 스플레이 트리	트리탐색
헤시테이블			해싱

 

📢   무순사전 ADT

• 무순리스트를 사용하여 구현된 사전  👉  사전 항목들을 임의의 순서로 리스트에 저장
  ( 이중연결리스트 또는 원형 배열을 사용 )

• 성능
  삽입 : O(1) 소요 👉 새로운 항목을 기존 리스트의 맨 앞 또는 맨 뒤에 삽입하면 되기 때문
  삭제 : O(N) 소요 👉 (최악의 경우)항목이 존재하지 않을경우, 리스트 전체를 순회해야 하기 때문
  탐색 : O(N) 소요 👉  (최악의 경우)항목이 존재하지 않을경우, 리스트 전체를 순회해야 하기 때문

• 효과적인 경우 : 소규모 사전, or 삽입은 빈번하나, 탐색이나 삭제는 드문 사전 ( Ex. 서버의 로그인 기록 )

 

📢   무순사전 선형탐색 알고리즘

Alg findElement(K)		// 배열 Ver.
	input Array[0..N-1], Key K
    output element with key K

i <- 0				// 첫번째 배열 인덱스 초기화
while(i < N)			// 배열 끝까지 갈때까지 반복 
	if(A[i].key == K)	// A[i].key != 목표 Key값
    	return A[i].key
    else				// A[i].key != 목표 Key값
    	i <- i + 1		
return NoSuchKey

================================================================

Alg findElement(K)		// 연결리스 Ver.
	input doubly linked list with header H and trailer T, Key K
    output element with Key K

i <- H.next			// 연결리스트 Header에 다음 노드로 초기화
while(i != T)			// 연결리스트의 끝 Tailer전까지 
	if(i.key == K)		// i.key == 목표 Key값
    	return i.elem
	else				// i.key == 목표 Key값
    	i <- i.next
return NoSuchKey

 

 

📢   순서사전 ADT

• 순서리스트를 사용하여 구현된 사전  👉  사전 항목들을 배열에 기초한 리스트에 키로 정렬된 순서로 저장

• 성능
  삽입 : O(N)  👉  새 항목을 삽입하기 위한 공간 확보를 위해, (최악의 경우) N개의 기존 항목을 이동해야 한다.
  삭제 : O(N)  👉  항목이 삭제된 공간을 기존 항목들로 메꾸기 위해 (최악의 경우) N개의 기존 항목 이동해야 한다.탐색 : O(log(N))  👉  이진탐색을 사용하면 가능하다.

• 효과적인 경우 : 소규모 사전, or 탐색이 빈번하나, 삽입 삭제는 드문 사전 ( Ex. 전화번호부 )

 

📢   이진탐색(Binary Search)

• 키값으로 된 "배열(Array)"에 기초한 리스트로 구현된 사전에 대해 탐색 작업을 수행한다.

• 배열의 키값들은 반드시 "정렬(Sorted)"되어 있어야 한다.

• 재귀적인 방식 비재귀적 방식이 두 가지 모두 구현 가능하다.

• 입력크기(N)의 로그 수(log(N))에 해당하는 수의 재귀(or 비재귀)를 수행한 후 정지한다. ( Ex. 스무고개 )

 

📢   재귀적 이진탐색

Alg findElement(K)
    input sorted Array A[0..N-1], K
    output element with key K
    
return rFE(K, 0, N-1)

=====================================
Alg rFE(K,l,r)			// l,r은 배열조사 범위의 왼쪽,오른쪽 인덱스

if(l > r)
	return NoSuchKey
mid <- (l + r)/2			// 재귀호출마다, 중앙 인덱스 mid값 구하고
if(K = Key(A[mid]))		// A[mid]값 = 찾아야될 key값, A[mid]값 반환 
	return element(A[mid])
elseif(K < Key(A[mid]))	// A[mid]값 > 찾아야될 key값, (범위를 l~(mid-1)로 재귀 이진탐색 재귀호출)
	return rFE(K, l, mid-1)
else					// A[mid]값 < 찾아야될 key값, (범위를 (mid+1)~r)로 재귀 이진탐색 재귀호출)
	return rFE(K, mid+1, r)

 

📢   비재귀적 이진탐색

Alg findElement(K)
	input sorted Array A[0..N-1], Key K
    output element with key K

l <- 0
r <- N-1
while(l <= r)			// 재귀호출 대신,반복문 사용
	mid <- (l + r) / 2	// 매 과정, 배열의 중앙 인덱스 mid 구하고
    if(K == Key(A[mid]))	// A[mid] == 목표 Key
    	return element(A[mid])
    elseif(K < key(A[mid]))	// A[mid] > 목표 Key
		r <- (mid - 1)
	else				// A[mid] < 목표 Key
    	l <- (mid + 1)
return NoSuchKey

📢   이진탐색 수행 예

 

📢   [ 참고 ] 재귀 알고리즘 👉 비재귀 알고리즘 전환하기 위한 일반적인 요령

1. 재귀호출을 반복문으로 대체한다.

2. 재귀의 매개변수를 반복문의 제어변수로 전환한다.

3. 최초의 재귀호출에 사용하는 매개변수 값을 반복문 진입 전 초기화로 전환한다.

4. 재귀의 BaseCase를 반복문의 종료 조건으로 전환한다.