[알고리즘 이론] 해시 테이블, 그래프, 트리, 힙

 

 

오늘은  자료구조의 나머지 부분인

해시 테이블, 그래프, 트리, 힙에 대해서

다뤄 보도록 하겠습니다. 

 

그럼 들어가 볼까요?

 

 

해시 테이블(Hash Table)

• 해시 테이블은 데이터를 키(key)와 값(value)의 쌍으로 저장하는 자료 구조입니다. python을 주로 다루는 분들은 Dictionary, java나 C++은 MAP이라는 자료 구조로 익숙할 것입니다. 
• 여기서 키(key)는 데이터에 접급하기 위한 고유한 식별자이며 값(value)은 키에 대응하는 실제 데이터입니다. 앞서 배운 배열을 기준으로 생각해보면 데이터의 위치를 나타내는 인덱스가 키 값이며 배열에 저장된 데이터가 실제 값인 것입니다. 다만 배열은 연솟된 메모리를 바탕으로 인덱스도 연속된 정수로 표현되지만 해시 테이블은 다양한 형태의 데이터 타입을 키로 선언할 수 있습니다.  

해시 테이블 구조

• 위 그림은 헤시 테이블의 구조와 동작 원리를 설명하고 있습니다. 키 값을 해시함수를 통해 정수 값으로 변환합니다. 이 떄 변환된 정수는 Bucket에 저장된 데이터를 찾는 역할을 합니다. Bucket은 실제 데이터를 저장하고 있는 배열로서 해시 함수를 통해 키 값을 입력함으로서 찾을 수 있습니다.  위의 테이블은 키 값으로 과일의 종류를 저장하고 이에 대응 되는 값으로 과일의 가격을 저장하고 있습니다. 여기서 오렌지의 가격을 알고 싶다면 해시 함수를 통해 오렌지의 가격이 저장된 테이블의 데이터 인덱스를 구하고 값을 불러오는 것입니다. 

💡해시 함수: 어떤 데이터(키)를 받아서, 고정된 크기의 값(해시값)으로 변환하는 함수

 

그래프 (Graph)

• 그래프는 정점(Vertex, 노드)와 간선(Edge, 연결)로 이루어진 비선형 자료 구조입니다. 앞서 배웠던 링크드 리스트가 한 줄로 이어진 사슬 같은 형태의 자료 구조라면, 그래프는 여러 개의 데이터가 복잡하게 얽혀있는 거미줄 같은 형태의 자료 구조입니다. 실생활에서 볼 수 있는 버스 노선도나 지하철 노선도 같은 형태의 자료 구조라 생각하면 이해가 쉬울 것입니다. 

지하철 노선도

 

• 그래프는 주로 데이터들 간의 복잡한 연결 관계를 표현할 때 사용하는 자료구조입니다. SNS 친구 관계라든가 지도에서 각 도로의 연결 상태를 표현할 때도 그래프를 사용하여 표현할 수 있습니다. 알고리즘에서는 각 데이터 사이의 연결 관계를 통해 거리나 경로를 구하는 방식으로 활용됩니다. 

그래프 예시

 

• 그래프는 연결하는 간선에 따라 여러 종류가 나뉠 수 있습니다.   

무방향 그래프	방향 그래프
가중치 그래프	DAG(Directed Acyclic Graph)

• 무방향 그래프: 방향이 없는 그래프로 정점 사이의 연결 관계로만 표현되는 그래프입니다. 
• 방향 그래프 : 간선에 방향이 존재하는 그래프입니다. 인스타그램으로 예시를 들면 누가 누구를 팔로우하고 있는지를 방향으로 표시하고 있는 경우라고 생각하면 됩니다. 나는 상대방을 팔로우하고 있지만 상대는 나를 팔로우하고 있지 않는 경우 처럼요.
• 가중치 그래프 : 가중치는 각 정점 사이의 연결 관계에 가중치가 존재하는 경우를 의미합니다. 주로 정점 사이의 거리나 비용 등을 의미합니다. 예를 들어 지도에서 각 지점 사이의 거리나 시간 등을 가중치로 하여 그래프로 표현할 수 있습니다. 이를 통해 데이터 사이의 최소 비용, 거리, 시간 등을 구할 수 있습니다. 
• DAG(Directed Acyclic Graph) : 방향 그래프 중 사이클이 없는 그래프를 DAG라고 합니다. 어느 한 정점에서 출발하여 다시 자기 자신으로 돌아올 수 있는 경우 사이클이 있다고 표현합니다. 

구현

• 그래프는 크게 두 가지 방법으로 구현할 수 있습니다. 첫 번째 방법은 배열을 사용하여 구현하는 것이며, 두 번째 방법은 해시 테이블을 사용하여 구현하는 것입니다.  

그래프 예시

• 그러면 위 그래프를 두 가지 방식을 사용하여 구현하도록 하겠습니다. 

# 인접 행렬을 통한 구현

# 정점 0, 1, 2번이 있고, 간선: (0-1), (1-2)
n = 3
graph = [[0]*n for _ in range(n)]
graph[0][1] = 1
graph[1][0] = 1
graph[1][2] = 1
graph[2][1] = 1

# 그래프 구현 모습(배열)
|   | 0 | 1 | 2 |
| - | - | - | - |
| 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 2 | 0 | 1 | 0 |


# 설명 
N개의 정점을 갖진 그래프가 존재할 경우
N x N 크기의 2차월 배열을 선언한 후 
각 정점의 연결 관계를 표현합니다.
각 배열의 값은 0과 1로 연결 여부를 표현합니다.
만약 가중치 그래프의 경우 가중치 값을 배열의 값으로
저장할 수 있습니다.

# 장점
1. 배열을 사용하기 때문에 연결 관계 확인이 빠릅니다. 
2. 구현이 간단합니다. 

# 단점
1. 간선의 개수와 관계 없이 N x N 크기의 공간을 소모하기 때문에
   공간 낭비가 큽니다. 
2. 정점의 수가 많으면 많을 수록 비효율적입니다.

 

# 인접 리스트를 통한 구현 

# 구현 예시
n = 3
graph = [[] for _ in range(n)]
graph[0].append(1)
graph[1].append(0)
graph[1].append(2)
graph[2].append(1)

혹은 

graph = {
    0: [1],
    1: [0, 2],
    2: [1]
}


# 설명
리스트와 해시 테이블을 조합하여 구현한 그래프입니다.
각 해시 테이블의 키 값으로 정점을 표현하고 
값으로 연결된 정점을 리스트로 저장합니다. 

# 장점 
1. 사용되는 정점과 간선의 수만큼만 데이터를 저장하기 때문에 메모리 효율이 좋습니다.
2. 연결된 노드를 탐색하는 데 유리합니다. 

# 단점
1. 리스트를 통해 구현하였기 때문에 두 정점 사이의 연결 관계를 확인하는 것이 느립니다.

 

트리 (Tree)

• 트리는 계층 계층적(hierarchical) 구조를 표현하는 비선형 자료 구조입니다. 하나의 루트 노드 (root)에서 여러 노드로 뻗어 나가는 구조를 가진 그래프입니다. 우리 생활에서 가장 흔하게 볼 수 있는 예시로는 가계도가 있습니다. 

AI로 생성한 가계도

• 트리에서 가장 중요한 개념 중 하나는 루트 노드로, 트리의 시작점이자 가장 위에 있는 노드이며, 부모가 없는 유일한 노드입니다. 루트 아래에는 여러 자식 노드가 연결되며, 자식을 가진 노드는 부모 노드라고 부릅니다. 같은 부모를 공유하는 노드들끼리는 형제 노드라고 하며, 트리 구조는 이러한 관계를 통해 위에서 아래로 가지를 뻗듯 확장됩니다.트리 구조에서는 깊이와 높이도 중요한 개념입니다. 깊이는 루트에서 특정 노드까지 도달하는 데 거치는 간선 또는 단계의 수를 의미하고, 높이는 루트에서 가장 먼 잎 노드까지의 최대 깊이를 말합니다. 즉, 트리의 높이는 가장 깊은 노드의 깊이와 같으며, 이는 트리의 전체적인 규모나 균형 상태를 판단할 때 사용됩니다. 이러한 개념들은 트리 탐색, 이진 탐색 트리, 힙, 트라이 등 다양한 트리 기반 알고리즘을 이해하고 구현하는 데 필수적인 요소입니다. 트리에서 더 이상 자식이 없는 노드를 잎(leaf) 노드 또는 말단 노드라고 하며, 이 노드는 트리 순회나 재귀 연산의 종료 조건으로 자주 사용됩니다. 

트리 자료 구조 예시

 

💡트리의 특징
1. N개의 노드는 항상 N-1 개의 간선을 가집니다. 
2. 사이클이 없는 그래프입니다. (DAG)
3. 하나의 루트에서 시작하여 하위로 뻗어나가는 형태입니다.

 

• 트리에는 다양한 종류가 존재하나 이것들에 대해서는 나중에 알아보도록 하겠습니다. 대표적인 개념 중 이진 트리와 완전 이진 트리만 설명하도록 하겠습니다. 

💡이진 트리 
- 각 노드가 최대 두 개의 노드를 가지는 트리 

💡완전 이진 트리 
- 왼쪽에서 오른쪽으로 차례대로 노드를 채우되 , 
  마지막 계층을 제외한 모든 계층이 가득 채워진 이진트리를 의미합니다.

 

• 트리는 보통 노드(Node) 기반 연결 구조를 사용합니다. 클래스와 포인터(혹은 참조)를 사용하여 각 노드가 자식 노드를 가리키도록 구현하는 것이 일반적입니다. 단 완전 이진 트리의 경우 배열로도 구현할 수 있습니다. 

# 이진 트리 구현 예시 

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None     # 왼쪽 자식 노드
        self.right = None    # 오른쪽 자식 노드

# 트리 구성
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')

 

• 완전 이진 트리에서 부모와 자식 노드 사이의 인덱스는 다음과 같은 규칙을 가집니다. 

관계	공식(i: 현재의 인덱스)
왼쪽 자식 노드	2 * i + 1
오른쪽 자식 노드	2 * i + 2
부모 노드	(i - 1) / 2 (정수 나눗셈)

 

• 이미지로 표현하면 다음과 같습니다.  

힙

• 힙은 크기 순서에 따라 부모-자식 관계를 가지도록 구현된 트리입니다. 주로 우선순위 큐(priority queue)를 구현할 때 주로 사용됩니다. 

💡힙의 특징
1. 완전 이진 트리 구조를 가진다. 
2. 힙 속성을 만족합니다. 
	최대 힙(Max Heap): 부모 노드 >= 자식 노드 
    최소 힙(Min Heap) : 부모 노드 <= 자식 노드 
3. 부모 자식 간의 우선 순위만 유지될 뿐 자료 구조 내부에서 
   값들이 정렬되어 있지는 않습니다.

 

• Heap은 완전 이진 트리이기 때문에 배열로 구현할 수 있습니다. Root 노드가 최댓값 혹은 최솟값으로 고정되어 있기 때문에 데이터의 최대, 최솟값을 찾기에 적합한 자료 구조입니다. 힙 자료구조의 작동 방식에 대해 자세히 알고 싶다면 아래 링크를 참조해주세요. 

Algorithm Canvas - 알고리즘 시각화 및 학습 사이트