[알고리즘] 00. 자료구조 리마인드

---

 

사담 공간

알고리즘을 본격적으로 포스팅하기에 앞서, 이전에 공부했던 자료구조를 리마인드해보자!

 

---

키워드

#스택 #큐 #트리 #그래프 #재귀

 

---

1. 스택

지난 글 참조

https://ll2ll.tistory.com/9

[자료구조] 06. 스택 (Stack)

 

LIFO : Last In First Out, 후입선출

데이터의 삽입과 삭제가 스택의 맨 위 지점 (top) 에서만 발생하는 자료구조.

재귀 포스팅에서 콜스택에 대해 다뤘었다.

 

[그림 1] 콜스택

 

왜 재귀에서는 이러한 "스택" 자료구조를 사용할까?

재귀 함수는 함수를 실행하던 도중 (같은 기능을 하는) 다른 함수가 실행되는 방식인데, 다른 함수의 실행이 종료되면 원래 실행되고 있던 함수의 위치로 돌아가야 한다.

이 때, 돌아갈 위치를 따로 기록하는 것보다는 실행될 함수를 하나씩 쌓아서 관리하며, 자연스럽게 없어지는 스택 방식을 활용하는 것이 효율적이다. 

 

 

2. 큐

지난 글 참조

 

https://ll2ll.tistory.com/10

[자료구조] 07. 큐 (Queue) & 덱 (Dequeue)

 

FIFO : First In First Out, 선입선출

데이터의 삽입은 큐 뒤쪽(rear)에서, 데이터의 삭제는 큐 앞(front)에서 이루어지는 자료구조.

이후 설명할 bfs에서도 "큐"가 사용된다.

 

"큐" 자료구조는 어떤 상황에서 사용될까?

처리해야 할 작업이 동시에 존재하는 상황 (ex. 상하좌우 경로탐색을 비롯한 BFS 문제) 의 경우 이에 대한 처리가 필요하다.

이 때 다음에 처리할 목표를 쌓아둔 후 접근하기 편하게 만들기 위해서 큐가 사용될 수 있다.

 

 

 

3. 그래프

지난 글 참조

 

https://ll2ll.tistory.com/21

[자료구조] 09. 그래프 - 개념과 표현방식

 

정점과 각 정점을 연결하는 간선으로 구성된 자료구조

 

그래프 문제는 대부분 해당 문제를 인접 행렬, 인접 리스트로 구현한 후 최소 비용을 탐색하거나 길을 찾는 문제가 출제된다.

큐에서 언급되었던 BFS와 다양한 그래프 탐색 방법 (BFS, DFS, 다익스트라...) 는 이후 그래프 활용 포스팅에서 다룰 계획이다.

 

"그래프" 자료구조는 어떤 상황에서 사용될까?

2차원 배열에서 길을 찾는 문제 (단순 경로 탐색, 최소 비용 및 최단 거리 구하기)

감시 카메라 문제와 같이 가장 적은 횟수로 무언가를 설치하는 문제로도 많이 나온다.

 

 

4. 트리

지난 글 참조

 

https://ll2ll.tistory.com/11

[자료구조] 08. 트리

 

계층적 관계를 표현하는 비선형 자료구조이자 그래프의 일종으로, 순환이 없는 연결 그래프

 

지난 포스팅에서도 다룬 이진트리에 이어 이진탐색트리와 힙트리도 다뤄보도록 하겠다.

 

이진 트리 (Binary Tree)

각 노드가 최대 2개까지의 자식 노드를 가질 수 있다.

이로 인해 트리가 커지더라도 작은 트리의 반복으로 치환이 가능해 구현이 간단해진다.

 

[그림 2] 완전이진트리 VS 완전이진트리가 아닌 것

특히 이전 시간에 보았던 완전이진트리의 경우 뒤에 다룰 힙 트리에 사용되므로 개념을 다시 한 번 짚고 넘어가자.

완전이진트리는 노드가 위->아래, 왼쪽 -> 오른쪽의 방향으로 완전히 채워져있는 트리 (빈틈이 없음) 이다.

 

 

이진탐색트리 (Binary Search Tree)

이진탐색트리(BST)는 이진트리 자료구조에서 한 가지 특성 (이진 검색 트리 특성)을 만족하도록 저장된다.

 

x가 BST의 한 노드일 때,
y가 x의 왼쪽 서브 트리의 노드일 경우 y.key <= x.key
y가 x의 오른쪽 서브 트리의 노드일 경우 y.key >= x.key

 

쉽게 말해서 데이터를 삽입할 때

• 해당 노드보다 작은 값은 왼쪽 서브트리
• 해당 노드보다 큰 값은 오른쪽 서브트리

위치에 삽입한다는 뜻이다.

 

이렇게 데이터를 저장하면 다음과 같은 이점이 존재한다.

• 중위 트리 순회 수행 시 트리의 모든 키를 정렬된 순서로 출력할 수 있음
• 데이터 탐색 시 자연스럽게 이분탐색으로 진행, 시간복잡도가 O(logn) 으로 줄어듦

 

 

 

힙 트리 (Heap Tree)

힙은 다음과 같은 특징을 가진 특수한 자료구조이다.

• 완전이진트리 형태를 가짐
• 부모 노드는 항상 자식 노드보다 크거나 작은 값을 가짐
  • 최대 힙 : 임의의 노드 값은 그 부모의 값보다 클 수 없음
  • 최소 힙 : 임의의 노드 값은 그 부모의 값보다 작을 수 없음
  • 즉 가장 큰(작은) 값은 루트에 저장되고, 서브 트리는 자신의 루트보다 크지 않은 (작지 않은) 값을 가진다.
• 새 노드를 추가할 때는 현재 노드 중 가장 마지막 위치에만 추가 가능
• 기존 노드를 삭제할 때는 루트 노드만 제거할 수 있음

노드를 추가하고 제거할 때마다 트리를 재구성해 힙의 특징을 유지하고, 이 과정을 heapify라고 한다.

 

힙 트리의 삽입과 삭제

[그림 3] 최대 힙 삽입 과정

1. 최대 힙에 새로운 노드 '52'가 현재 마지막 위치에 삽입됨
2. 최대 힙의 성질 (임의의 노드 값은 그 부모의 값보다 클 수 없음) 로 인해 heapify가 이뤄짐
3. 부모 노드와의 교환 이뤄짐
4. 전체 트리가 최대 힙의 성질을 만족하므로 heapify 완료
5. 노드 삽입 완료

 

[그림 4] 최대 힙의 삭제 과정 - 1

1. 현재 힙의 루트 노드 '100'이 삭제됨
2. 마지막 노드인 '19'를 루트 노드로 올리기
3. 최대 힙의 성질 (임의의 노드 값은 그 부모의 값보다 클 수 없음) 로 인해 heapify가 이뤄짐

[그림 5] 최대 힙의 삭제 과정 - 2

4. 부모 노드와의 교환 이뤄짐

5. 전체 트리가 최대 힙의 성질을 만족하므로 heapify 완료

6. 노드 삭제 완료

 

 

힙 트리의 구현

힙 트리는 완전이진트리 자료구조에서 heapify 과정을 추가하면 배열, 연결리스트 모두 구현이 가능하다.

최대 힙 heapify 함수 구현 (with python)

 

# 배열 A와 인덱스 i를 입력으로 받을 때
def parent(i):
    return i//2

def left(i):
    return 2*i

def right(i):
    return 2*i + 1

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    
    # 새로운 노드 인덱스와 왼쪽, 오른쪽 노드 비교
    if l <= len(A) and A[l] > A[i]:
        largest = l
    
    else:
        largest = i
    
    if r <= len(A) and A[r] > A[largest]:
        largest = r
    
    # i가 최대 힙이 아닐 경우 -> heapify 과정 필요
    if largest != i:
        # 위치 스왑하기
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest) # 재귀 형식으로 호출

 

이번 포스팅에서는 파이썬에서 제공하는 heapq 라이브러리를 통한 구현을 위주로 알아보자.

 

heapq는 최소 힙 트리의 구현 및 조작 기능을 제공한다.

https://docs.python.org/ko/3/library/heapq.html

heapq — Heap queue algorithm

 

• 인덱스가 0부터 시작하는 배열을 사용한다
• 최소 힙이므로 heap[0]은 언제나 전체 힙의 최소값이다.
• sort() 메서드는 힙의 불변성을 유지한다.
  • 힙의 불변성 : 앞서 설명한 힙의 조건이 유지된다는 뜻

 

heapq 클래스에서 제공되는 메서드는 아래와 같다.

메서드(인자)	설명
heappush(heap, item)	item 값을 힙에 삽입
heappop(heap)	불변성을 유지하며 최소값(루트값)을 반환
heapify(x)	리스트 x를 힙으로 제자리 변환
heapreplace(heap, item)	heappop + heappush
merge(*iterables, key=None, reverse=False)	여러 정렬된 입력을 단일 정렬 출력으로 병합
nlargest(n, iterable, key=None)	n개의 가장 큰 요소로 구성된 리스트 반환
nsmallest(n, iterable, key=None)	n개의 가장 작은 요소로 구성된 리스트 반환

 

그럼 최대 힙은??

간단하다. 음수를 붙여주면 된다!

앞에서 봤던 힙 트리 그림을 heapq로 구현해보자.

import heapq

heap = [-100, -36, -17, -19]
heapq.heapify(heap)
print(heap)

heapq.heappush(heap, -52)
print(heap)

heapq.heappop(heap)
print(heap)


print(heapq.nlargest(3, heap))
print(heapq.nsmallest(3, heap))

[그림 6] 실행 결과

 

우선순위 큐와 힙 정렬의 내용은 정렬 포스팅에서 다뤄보도록 하겠다.