사전은 특정 키에 대한 특정 원소가 매핑되는 1대1 쌍 항목들의 모임으로 구성된다. 사전 ADT라 함은 이를 추상 데이터구조로 모델링한 것이다.
지난 정렬 파트에서는 우선순위 큐를 사용하거나 리스트의 데이터 항목들이 key로만 구성된 것을 가정하고 정렬 작업을 수행했다. 하지만 현실적으로 데이터 항목은 포인터만 저장하고 각 포인터는 키, 원소의 쌍 항목 데이터를 가리키는 방식으로 구현되는 경우가 많다.
사전 ADT의 주요 작업은 탐색, 삽입, 삭제다. 키를 탐색해 키와 연관된 원소를 찾는 것이 주요 작업이 된다.
사전ADT에는 무순사전 ADT와 순서사전ADT 2가지가 있다.
탐색
사전 ADT에서 탐색은 특정 key와 연관된 원소를 찾는 작업을 말한다. 이 때의 key는 유일키냐 중복키냐에 따라 전제가 달라질 수 있다. db의 pk나 고유하게 식별이 되는 무언가라면 유일키겠고 중복이 허락되면 중복키로 정의가 되겠다.
무순사전 ADT
무순사전의 대표적인 예시는 log file이 있다. log가 찍힐 때마다 한 줄 한 줄 기록이 찍히며 누적된다.
무순사전의 삽입 시간은 O(1)이다. 탐색과 삭제는 O(N)이 된다. 키를 찾기 위해 전체를 훑어야 할 수 있다. 다시 말해 무순사전은 삽입이 빠르지만, 탐색과 삭제에서 리스크가 있다.
무순사전은 선형탐색을 수행한다.
Alg linearSearch(k)
input list L, key k
output element with k
i <- L.root()
while(L.isValid(i)){
if(L.key(i) = k){
return L.element(i)
} else{
L.advance(i)
}
}
return NoSuchKeyi번째 위치에 L이 유효할 때까지 while문을 돈다. key를 찾으면 그 원소를 리턴해주고 그게 아니라면 i+1번째로 i를 전진시킨다.
선형탐색의 성능은 O(N)이다. 순서대로 쭉 일렬로 훑고 있기 때문에 선형이라 하지 않았을까
순서사전 ADT
순서사전의 대표적인 예시는 일람표가 있다. 다수의 항목을 순서대로 정리한 기록이다.
순서사전의 탐색은 이진탐색을 사용하며 O(logN) 시간 소요된다. 삽입과 삭제는 O(N)이 걸린다. 삽입 항목을 위한 공간 확보를 위해 최악의 경우 N개를 이동시켜야 하기 때문이다. 그리고 삭제 항목을 메꾸기 위해 최악의 경우 N개를 이동시켜야 하기 때문이다. 따라서, 순서사전은 삽입, 삭제보다 탐색이 빈번한 경우에 효과적으로 쓰인다.
선형탐색 개선
//순서사전의 선형탐색 개선
Alg linearSearch(k)
input sotred list L, key k
output element with k
i <- L.root()
while(L.isValid(i)){
if(L.key(i) = k){
return L.element(i)
} else if(L.key(i) > k){ //k값을 key(i)가 넘었다면 더 이상 찾을 필요가 없음
return NoSuchKey
} else{
L.advance(i)
}
}
return NoSuchKey순서사전은 이진탐색을 사용하지만 선형탐색을 조금 개선할 수도 있다.
무순사전의 그것과 달라진 점은 else if문이다. 모든 키값이 순서대로 정렬되어 있기 때문에 키값이 우리가 찾고자하는 것보다 커지면 더 이상 찾을 필요가 없어진다. 따라서 평균적으로 N의 절반을 탐색한다.
그러나 입력 크기에 따라 시간복잡도는 선형으로 증가할 것이고 여전히 O(N) 시간 소요된다.
이진탐색
이진탐색은 순서사전의 유리한 탐색 전략이다. 이진탐색은 키로 정렬된 배열에 기초한 사전에 대해 탐색 작업을 한다.
Alg binarySearch(k, p, r)
input key k, sorted array A[p...r]
output element with k
if(p > r)
return
q <- (p+r)/2
if(A.key(q) = k){
return A.element(q)
} else if(A.key(q) > k){
return binarySearch(k, p, q-1)
} else{ //A[q]의 키값이 더 작음
return binarySearch(k, q+1, r)
}뭔가 분할정복 정렬 알고리즘들과 비슷한 냄새가 나는 것 같다. 그러나 이진탐색은 if문을 통해 k값과 배열의 가운데 원소를 비교하여 이등분된 2개의 범위 중 하나로 탐색 범위를 추려나가는 알고리즘이고 분할정복은 이등분된 2개의 범위 모두를 고려한다.
이진탐색의 성능은 O(logN)이다. 배열이 아니라 연결리스트로 구현된 경우, p와 r 사이의 q 인덱스로 접근하기 위해 O(N) 시간이 걸리기 때문에 O(N)이 된다. 이진탐색의 대표적인 예시는 스무고개다. 약 100만개의 정답 후보가 있더라도 절반씩 추려나갈 수 있다면 20번의 질문으로 정답을 추출할 수 있다.
참고 : 국형준. 알고리즘 원리와 응용. 21세기사, 2018.
