파이썬을 이용한 탐색과 맵 자료구조

이번 포스팅에서는 탐색, 맵, 엔트리, 딕셔너리에 대해서 살펴봅시다.

탐색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업입니다.

맵 또는 딕셔너리는 탐색을 위한 자료구조로 엔트리 또는 키를 가진 레코드의 집합 입니다.

사전의 구성요소는?

엔트리

키(key) : 영어 단어와 같은 레코드를 구분할 수 있는 탐색 키

값(value): 단어의 의미와 같이 탐색키와 관련된 값

파이썬의 딕셔너리 구조는 키와 값으로 이루여져 있습니다.

맵을 구현하기에 앞서 추상형 자료구조 ADT를 고려를 해봅시다.

search(key) 탐색키를 가진 레코드를 찾아서 반환

insert(entry) 주어진 엔트리를 맵에 삽입

delete(key) 탐색키를 가진 레코드를 찾아서 삭제

맵을 구현하는 방법은 리스트를 이용하는 방법 정렬/비정렬, 이진 탐색 트리, 해싱구조등이 있습니다.

먼저 간단한 탐색 알고리즘 순차 탐색과 이진 탐색을 살펴봅시다.

순차 탐색(sequential search)

만약 내가 종이사전에서 단어를 찾고자 하는데, 정렬이 되어 있지 않다면? 어쩔수 없이 맨처음부터 찾아보게 될것입니다. 이를 순차 탐색이라고 하지요, 최선의 경우는 한번만에 찾는 1이고 최악의 경우는 마지막에 존재하기에 n입니다.

그렇다면 평균적인 비교 횟수는 (1+n)/2가 되겠네요

def sequential_search(A,key,low,high):
    for i in range(low,high+1):
    	if A[i].key==key:
    		return i
    return None

순차 탐색 알고리즘은 간단합니다. 특정 구간의 처음부터 끝까지 돌려서 비교를 해보고 없으면 None를 반환해주면 됩니다. 시간 복잡도는 n이겠네요

이진 탐색(binary search)

이진 탐색은 binary 둘로 나눈다는 의미를 지니고 있습니다. 흔히 업다운 게임을 떠올리시면 쉬울 겁니다. 임의의 수를 찾는데 1~100 사이에 있을 겨우 50을 먼저 부르는게 유리하지요

다만 정렬된 배열의 탐색에 적합합니다. 장점은 빠르게 찾을 수 있습니다. 10억명중 특정한 이름을 찾기 위해서는 30번의 비교로 찾을 수 있지만 순차 탐색의 경우 평균적으로 5억번의 시도를 해야합니다.

34라는 값을 찾기 위해서 절반씩 나누어서 반복하니 4단계면 값을 찾아 냈습니다. 순차 탐색이었다면 11번이 소요됩니다.

def binary_search(A,key,low,high):
    if(low <= high):
    	middle = (low + high)//2
        if key === A[middle].key:
        	return middle
        elif (key<A[middle].key):
        	return binary_search(A,key,low,middle -1)
        else:
        	return binary_search(A,key,middle+1,hihg)
    return None

일단 찾는데 low와 high가 잘 들어갔는지 대수비교를 하는 것으로 시작을 합시다.

그리고 중간값을 low와 high의 중간지점인데, 5.5번째라는 것은 존재하지 않으니 몫 연산자 //을 사용하게 됩니다. 자연스럽게 소수점 버림으로 가지요

첫번째, 중간에 있는 값이 내가 찾던 값일 경우 -> 바로 반환 끝

key가 중간 값 보다 작을 경우 low~middle-1 까지 해서 재탐색

key가 중간 값 보다 클 경우 middle+1 ~ high 까지 재탐색

이렇게 순환을 했지만 발견되지 않는다면 반환 값은 없음이 된다.

이제 맵을 응용해서 나만의 단어장을 만들자

리스트를 이용한 순차 탐색 맵으로 한번 그리고 내장되어 있는 파이썬의 딕셔너리를 이용해서 한번 해보자

맵 ADT를 구현

– 리스트를 이용해 순차 탐색 맵을 구현하는 방법

– 리스트를 정렬해서 이진 탐색 맵을 구현하는 방법

– 선형조사법으로 해시 맵을 구현하는 방법

class Entry:
    def __init__(self, key, value):
    	self.key = key
        self.value = value
    def __str__(self):
    	return str("%s:%s"%(self.key, self.key))

엔트리 클래스는 이렇게 구성됩니다. key과 value 그리고 print 중복연산을 위해서 __str__을 이용합시다.

다음은 리스트를 이용한 순차 탐색 맵입니다.

class SequentialMap:
    def __init__(self):
    	self.table=[]
    def insert(self, key, value):
    	self.table.append(Entry(key,value))
    def search(self, key):
    	pos = sequential_search(self.table, key, 0, self.size()-1)
        if pos is not None: return self.table[pos]
        else : return None
    def delete(self,key)
    	for i in range(self.size()):
        	if self.table[i].key == key
            	self.table.pop(i)
                return

순차 탐색에서 생성자는 table라는 리스트로 시작을 합시다.

삽입은 간단하게 엔트리 클래스를 append 리스트 함수로 더하고

찾기는 앞서 만든 순차 탐색 알고리즘을 통해서 찾게 됩니다. 만약 해당 하는 위치를 발견하게 된다면 해당 table를 반환하게 되고 없다면 None를 돌려줍니다.

삭제의 경우 처음부터 key를 찾게 되는데 발견할때에는 pop를 이용해서 리스트에서 제거를 해줍시다,.

test 코드

map = SequentialMap()
map.insert('data','자료')
map.insert('structure','구조')
map.insert('sequential search','선형탐색')
map.insert('gmae','게임')
map.insert('binary search','이진 탐색')
map.display('나의 단어징')

print("탐색 : gmae --> ",map.search('gmae'))
print("탐색 : over --> ",map.search('over'))
print("탐색 : data --> ",map.search('data'))

map.delete('gmae')
map.display("나의 단어장 :")

파이썬의 딕셔너리를 이용하면 사실 간단하게 똑같은 기능을 수행 할 수 있습니다.

d = {}
d['data'] = '자료'
d['structure'] = '구조'
d['sequential search'] = '선형 탐색'
d['game'] = '게임'
d['binary search'] = '이진 탐색'
print("나의 단어장:")
print(d)

if d.get('game') : print("탐색 : game --> ", d['game'])
if d.get('over') : print("탐색 : over --> ", d['over'])
if d.get('data') : print("탐색 : data --> ", d['data'])

d.pop('game')
print("나의 단어장:")
print(d)

d = {}을 통해서 딕셔너리 구조를 선언을 하고 d[키]=값을 그대로 입력을 하면 됩니다.

딕셔너리에서 값을 찾고 싶다면 d.get[키]가 되며, d[키]를 호출하면 해당 값이 나오게 됩니다.

튜플이 아니기에 제거도 가능하며 pop(키)를 이용하면 제거 역시 마찬가지로 됩니다.