[자료구조] 비선형 자료구조(힙, 우선순위 큐, 맵, 셋, 해시테이블)

비선형 자료구조(힙, 우선순위 큐, 맵, 셋, 해시테이블)

책 『면접을 위한 CS 전공지식 노트』를 바탕으로 스터디를 진행하면서 공부한 내용을 정리했다.

 

~ 목차 ~

1. 힙
2. 우선순위 큐
3. 맵
4. 셋
5. 해시테이블

 

비선형 자료 구조란 요소가 일렬로 나열되어 있지 않고 순서나 관계가 복잡한 자료구조를 말한다.

종류로는 트리, 그래프, 힙, 우선순위 큐, 맵, 셋, 해시테이블이 있다. (아래에서는 힙부터 설명한다.)

 

1. 힙

  - 힙은 완전 이진 트리 기반의 자료구조로, 각 노드의 값이 특정 규칙에 따라 정렬된 구조이다.

    - 최소힙(Min-Heap): 루트 노드에 가장 작은 값이 위치한다.

    - 최대힙(Max-Heap): 루트 노드에 가장 큰 값이 위치한다.

 

  - 힙의 삽입과 삭제는 아래와 같이 이루어진다.

    - 삽입: 새로운 노드를 힙의 마지막 노드에 삽입한 뒤, 새로운 노드를 부모노드들과 교환하면서

                힙의 성질(최대 힙 또는 최소 힙)을 만족시킨다.

    - 삭제: 항상 루트 노드(최대 힙의 경우 최대값, 최소 힙의 경우 최소값)를 제거한다.

 

2. 우선순위 큐

  - 우선순위 큐는 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 먼저 제공되는 자료구조이다.

  - 힙을 기반으로 구현되고, 삽입과 삭제를 통해 가장 높은 또는 낮은 우선순위의 작업을 효율적으로 관리한다.

 

3. 맵

  - 맵은 키와 매핑된 값의 쌍으로 이루어진 데이터를 저장하는 자료구조이다.

  - 데이터를 빠르게 검색, 삽입, 삭제하는데 유용하다.

# 맵 생성 및 초기화
my_map = {}
my_map['apple'] = 3
my_map['banana'] = 5

# 값 조회
print(my_map['apple'])  # 출력: 3

# 키 존재 여부 확인
print('banana' in my_map)  # 출력: True

# 값 삭제
del my_map['banana']

# 전체 키-값 출력
for key, value in my_map.items():
    print(key, value)  # 출력: apple 3 \n banana 5

 

4. 셋

  - 셋은 중복되지 않는 고유한 요소들을 저장하는 집합 자료구조이다. 순서를 보장하지 않는 특징이 있다.

  - 빠른 검색, 중복 제거, 집합 연산에 유용하다.

# 빈 셋 생성
my_set = set()

# 초기 값으로 셋 생성
my_set = {1, 2, 3, 4, 5}
print(my_set)  # 출력: {2, 5, 3, 4, 1} (순서는 다를 수 있음)

my_list = [1, 2, 2, 3, 3, 4]
unique_set = set(my_list)  # 중복 제거
print(unique_set)  # 출력: {1, 2, 3, 4}

 

5. 해시테이블

  - 해시테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다.

  - 시간 복잡도가 $O(1)$에 가깝기 때문에 빠른 접근이 필요한 상황에서 사용된다.

my_dict = {}
my_dict['apple'] = 3
my_dict['banana'] = 5

# 탐색
print(my_dict['apple'])  # 출력: 3

# 삭제
del my_dict['banana']
print(my_dict)  # 출력: {'apple': 3}

 

 

 

 

참고문헌

[1] 주홍철, 면접을 위한 CS 전공지식 노트, 서울: 길벗, 2022.