[자료구조] 탐색 1. 탐색과 맵 (Map)

우리는 매일 인터넷에서 원하는 정보를 찾고, 사전 등에서 궁금한 내용을 찾아본다.
그러나 매우 방대한 인터넷에서, 우리가 알고 싶은 정보를 어떻게 찾아낼 수 있는 걸까?

이 개념을 자료구조에도 적용해보자. 우리가 저장한 데이터에서 정보를 찾아내는 것을 탐색이라고 한다. 빠르고 효율적인 탐색을 위해서 데이터를 잘 정리해둘 필요가 있다.

사전의 경우 가나다 순이 아니고 뒤죽박죽 정리되어 있다면… 아마 우리가 원하는 정보를 탐색할 수 없을 것이니까…

탐색은 레코드(record)의 집합(table)에서 원하는 레코드를 찾는 작업이다. 레코드들은 서로를 구별하여 인식할 수 있는 키(key)를 가지고 있는데 이를 탐색 키(search key)라고 한다.

 

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

 

원활한 탐색을 위해 고안된 효율적인 자료구조로는 맵(Map)이 있다. 파이썬을 주로 다루는 프로그래머들에게는 맵보다는 딕셔너리(Dictionary)라는 용어가 더 익숙할 것이다.
맵은 키(key)-값(value)의 쌍으로 이루어진 엔트리(entry)의 집합이다. 키를 가지고 값을 탐색할 수 있는 매우 효율적인 자료구조로 볼 수 있다.

 

맵의 기능

• search(key): 탐색키 key를 가진 레코드를 찾아 반환한다.
• insert(entry): 주어진 entry를 맵에 삽입한다.
• delete(key): 탐색키 key를 가진 레코드를 찾아 삭제한다.

---

맵의 구현

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

class SequentialMap: # 리스트로 구현한 맵
    def __init__(self):
        self.table = []

    def size(self):
        return len(self.table)

    def display(self, msg):
        print(msg)
        for i in self.table:
            print(" ", i)

    def insert(self, key, value):
        self.table.append(Entry(key, value)) # 정렬하지 않고 맨 뒤에 append 하니까 순차 탐색으로 search 해야 함.

    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

시간복잡도
insert(): O(1)

pop(), delete(): O(n)

---

해시와 체이닝을 이용해서도 맵을 구현할 수 있다…

그러나 아직 해시를 공부하지 않았으므로 추후에 해시를 공부하면서 설명하도록 하겠다!

 

 

작성일자: 2023-03-11