그래프
그래프(graph)는 데이터를 포함하는 정점(vertex)과 정점을 잇는 간선(edge)으로 구성된 자료구조다.
정점은 노드(node)라고도 한다.
일반적으로 그래프는 각 용어의 영문 앞 글자를 따서 G = (V, E)로 표현한다.
그래프 용어
•
인접(adjacent)
두 정점이 간선으로 연결되어 있으면 인접하다고 한다.
•
차수(degree)
정점에 연결된 간선의 수를 나타낸다.
•
진입 차수(in-degree)
해당 정점으로 향하는 간선의 수를 의미한다.
•
진출 차수(out-degree)
해당 정점에서 나가는 간선의 수를 의미한다.
•
경로(path)
한 정점에서 다른 정점으로 이어지는 정점들의 리스트를 뜻한다.
Path(A, B) = [A, e1, B] or [A, e3, C, e2, B]
•
경로 길이(path length)
경로를 구성하는 간선의 수이다.
•
단순 경로(simple path)
모두 다른 정점으로 구성된 경로를 의미한다.
•
사이클(cycle)
한 정점에서 시작해 같은 정점으로 돌아올 수 있는 경로를 의미한다.
그래프의 종류
•
무방향 그래프(undirected graph)
무방향 그래프는 간선에 방향성이 없는 그래프다.
두 정점이 연결되어 있을 때 순서가 없으므로 (A, B)와 (B, A)는 동일한 간선을 의미한다.
정점의 개수가 n일 때 최대 간선의 개수는 n x (n - 1) / 2 이다.
•
방향 그래프(directed graph)
방향 그래프는 간선에 방향성이 있는 그래프다.
두 정점이 연결되어 있을 때 A에서 B로 향하는 간선을 <A, B>로 표기한다.
따라서 <A, B>와 <B, A>는 다른 간선을 의미한다.
정점의 개수가 n일 때 최대 간선의 개수는 n x (n - 1) 이다.
•
가중치 그래프(weighted graph)
간선에 비용이나 가중치가 할당된 그래프이다.
•
완전 그래프(complete graph)
간선을 최대로 가진 그래프이다.
정점의 개수가 n일 때 무방향 그래프의 간선 수가 n x (n - 1) / 2 이면 연결 그래프이다.
•
유향 비순환 그래프(Directed Acyclic Graph)
방향 그래프이면서 사이클이 없는 그래프이다.
•
부분 그래프(sub graph)
기존 그래프에서 일부 정점 또는 간선을 제외한 그래프이다.
경로 탐색
시작 정점이 주어졌을 때 간선을 거쳐 모든 정점을 탐색하는 경로를 질문하는 그래프 탐색 문제가 코딩 테스트에 자주 출제된다.
•
너비 우선 탐색(Breadth-First Search)
탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식이다.
먼저 발견한 정점과 인접한 정점들을 탐색하면서 큐에 삽입한다.
이럴 경우 이전에 방문한 정점을 큐에 삽입하면 끊임없이 탐색을 반복하게 될 수 있다.
따라서 탐색한 정점을 큐에 넣기 전에 이전에 방문했는지 반드시 확인해야 한다.
너비 우선 탐색을 하면 비가중치 그래프에서 시작 정점부터 특정 정점까지의 최단 거리를 알 수 있다.
•
깊이 우선 탐색(Depth-First Search)
깊이 우선 탐색은 시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색한다.
만약 최대 깊이인 정점에 도달했다면 방문한 정점들은 역순으로 재방문하면서 탐색 가능한 정점이 있는지 확인한다.
탐색 가능한 정점이 있다면 해당 정점부터 다시 최대 깊이 정점까지 탐색을 진행한다.
깊이 우선 탐색은 재귀 호출 또는 스택으로 구현할 수 있다.
깊이 우선 탐색을 하면 특정 정점에서 다른 정점까지의 경로를 알 수 있다.
이때 깊이 우선 탐색을 스택이 아닌 재귀 호출로 구현하면 방문해야 할 정점을 저장할 필요가 없어서 너비 우선 탐색 대비 저장 공간을 적게 사용한다.
트리
트리(tree)는 그래프의 한 종류로 사이클이 없어서 계층적 관계를 표현할 수 있다.
트리 용어
•
루트 노드(root node)
부모 노드가 없는 노드로 트리에는 하나의 루트 노드가 존재한다.
•
부모 노드(parent node)
루트 노드 방향으로 연결된 노드다.
•
자식 노드(child node)
루트 노드의 반대 방향으로 연결된 노드다.
•
단말 노드(leaf node)
자식 노드가 없는 노드다.
•
형제 노드(sibling node)
부모 노드가 같은 노드다.
•
레벨(level)
루트 노드로부터 노드의 상대적 위치를 의미한다.
일반적으로 루트 노드의 레벨은 0이다.
•
높이(height)
트리의 최대 레벨 + 1을 의미한다.
•
차수(degree)
자식 노드의 개수를 나타낸다.
이진 트리
이진 트리(binary tree)는 자식 노드가 최대 2개인 트리다.
•
완전 이진 트리(complete binary tree)
트리의 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있으며 마지막 레벨은 왼쪽에서부터 오른쪽으로 노드가 채워져 있는 이진 트리다.
•
포화 이진 트리(perfect binary tree)
트리의 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리다.
따라서 포화 이진 트리는 완전 이진 트리라고 할 수 있다.
•
이진 탐색 트리(Binary Search Tree)
한 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성되고, 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성된 트리다.
균형 잡힌 이진 탐색 트리에서는 루트 노드와 가까운 노드일수록 검색해야 하는 노드 개수가 절반으로 줄어든다.
따라서 값을 검색하는데 O(logn)이 소요된다.
하지만 균형이 잡히지 않은 이진 탐색 트리에서는 검색하는데 시간 복잡도 O(n)이 소요되므로 이진 탐색 트리를 이용하는 장점이 사라진다.
그래서 완전 이진 트리로 이진 탐색 트리를 구성하려면 균형 이진 탐색 트리(balanced BST)가 필요하다.
균형 이진 탐색 트리의 대표적인 예로는 레드-블랙 트리와 AVL 트리가 있다.
•
레드-블랙 트리
레드-블랙 트리는 노드가 검은색 또는 빨간색인 트리로 정해진 규칙을 만족하면서 균형을 유지하는 트리다.
레드 블랙 트리는 이진 탐색 트리이면서 추가로 충족해야 하는 조건이 있다.
트리의 데이터에 대한 연산을 수행했을 때 다음 조건을 만족하지 못하면 회전과 색 변환을 해서 노드를 재배치해야 한다.
◦
모든 노드는 검은색 또는 빨간색이다.
◦
루트 노드는 검은색이다.
◦
모든 단말 노드(NIL)는 검은색이다. 단말 노드는 트리의 끝을 나타내며 값을 갖지 않는다.
◦
빨간색 노드의 자식 노드는 검은색이며 빨간색 노드가 연속으로 나올 수 없다.
◦
루트 노드에서 임의의 단말 노드까지 경로에 검은색 노드의 개수는 모두 같다.
•
AVL 트리
AVL 트리는 자가 균형 이진 탐색 트리로 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이를 유지해 균형을 잡는 트리다.
높이 차이를 알려면 왼쪽 서브 트리의 높이에서 오른쪽 서브 트리의 높이를 뺀 값인 BF(balance factor)를 사용한다.
◦
왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이는 최대 1이다.
◦
왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1보다 커지면 균형을 잡아 높이 차이를 줄인다.
AVL 트리에는 LL, RR, LR, RL이라는 4가지 불균형 상황이 있다.
불균형 상황이면 트리를 회전해 균형을 유지한다.
오른쪽 회전은 해당 노드를 중심으로 시계 방향 회전을, 왼쪽 회전은 해당 노드를 중심으로 반시계 방향 회전을 의미한다.
◦
LL 불균형
왼쪽으로 불균형을 이룰 경우에 가운데 노드를 중심으로 오른쪽으로 회전해서 균형을 맞춘다.
◦
RR 불균형
오른쪽으로 불균형을 이룰 경우에 가운데 노드를 중심으로 왼쪽으로 회전해서 균형을 맞춘다.
◦
LR 불균형
왼쪽, 오른쪽으로 불균형을 이룰 경우 마지막 레벨에 위치한 노드를 중심으로 왼쪽으로 회전한 후 다시 오른쪽으로 회전해서 균형을 맞춘다.
◦
RL 불균형
오른쪽, 왼쪽으로 불균형을 이룰 경우 마지막 레벨에 위치한 노드를 중심으로 오른쪽으로 회전한 후 왼쪽으로 회전해서 균형을 맞춘다.
이진 탐색 트리에서 데이터의 추가, 삭제 연산
•
데이터 추가
이진 탐색 트리에서 데이터 추가는 루트 노드부터 차례대로 값을 비교해 나가면서 삽입할 자리를 찾는 방식이다.
추가하려는 데이터가 비교하는 노드보다 값이 큰 경우는 오른쪽 자식 노드와 비교를 수행하고, 작은 경우는 왼쪽 자식 노드와 비교를 수행한다.
•
데이터 삭제
이진 탐색 트리에서 데이터를 삭제하는 경우는 자식 노드의 개수에 따라 3가지로 나눌 수 있다.
◦
자식 노드가 없는 경우
해당 노드만 삭제하면 된다.
◦
자식 노드가 1개인 경우
자식 노드를 삭제한 노드의 위치로 옮기면 된다.
◦
자식 노드가 2개인 경우
오른쪽 서브 트리에서 가장 작은 값을 삭제한 노드 위치로 옮기면 된다.
또는 왼쪽 서브 트리에서 가장 큰 값을 삭제한 노드 위치로 옮겨도 된다.
우선순위 큐
우선순위 큐(priority queue)는 우선순위가 높은 데이터가 먼저 나오는 자료구조다.
큐와 동일하게 데이터 삽입과 삭제 연산을 지원한다.
데이터 삭제 연산을 수행하면 우선순위가 가장 높은 데이터를 얻을 수 있다.
우선순위 큐를 구현하는 방식은 배열, 연결 리스트, 완전 이진 트리인 힙이 있다.
각 구현 방식의 시간 복잡도는 다음과 같다.
일반적으로 가장 효율적인 방식인 힙을 사용한다.
힙
힙(heap)은 완전 이진 트리로 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조다.
우선순위 큐를 구현하는데 자주 사용한다.
•
최대 힙(max heap) : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리다.
•
최소 힙(min heap) : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리다.
삽입 연산
힙에 데이터를 삽입할 때는 힙의 맨 끝에서 이루어진다.
부모 노드와 우선순위(최댓값 또는 최솟값)를 비교해 부모 노드보다 우선순위가 높으면 위치를 바꾸면서 루트 노드까지 비교한다.
삭제 연산
힙에서 데이터 삭제는 우선순위가 가장 높은 노드를 삭제하는 연산이다.
즉, 루트 노드를 삭제하게 된다.
삭제한 후에는 루트 노드 자리에 힙의 마지막 노드(마지막 레벨의 가장 오른쪽 노드)를 옮긴 후 힙을 재정렬한다.
해시 테이블
해시 테이블(hash table)은 하나의 키(key)에 대해 하나의 값(value)을 저장하는 형태의 자료구조다.
키는 해시 함수(hash function)를 사용해 해시를 얻을 수 있다.
해시는 값이 저장되어 있는 해시 테이블의 인덱스를 찾을 수 있는 값이다.
해시 함수에 키를 넣으면 해시 테이블에서 매칭되는 결과 값에 한 번에 접근할 수 있다.
따라서 연산은 평균적으로 O(1)의 시간 복잡도를 갖는다.
하지만 해시 테이블에는 해시 충돌이라는 단점이 있다.
해시 충돌은 서로 다른 키에 대해 같은 해시가 도출되는 것을 말한다.
해시 충돌 문제를 해결하기 위한 방법에는 체이닝과 개방 주소법이 있다.
•
체이닝(chaining)
해시 충돌이 발생하면 같은 해시가 나오는 키의 값을 연결 리스트에 저장하는 방식이다.
연결 리스트에 노드를 저장하므로 저장 공간에 대한 제약이 적다는 장점이 있다.
하지만 하나의 해시(인덱스)에 노드가 몰릴 수 있다는 단점이 있다.
•
개방 주소법(open addressing)
해시 충돌이 발생했을 때 해당 해시가 아닌 비어 있는 공간에 값을 저장하는 방식이다.
◦
선형 조사법(linear probing)
h[n]에서 해시 충돌이 발생하면 h[n+1], h[n+2]와 같이 다음 인덱스로 이동하면서 빈 공간을 찾는 방식이다.
선형 조사법은 충돌이 발생하면 다음 인덱스에 데이터를 저장하므로 특정 인덱스 범위에 데이터가 몰리는 군집화 현상이 나타나는 단점이 있다.
◦
이차 조사법(quadratic probing)
이차는 거듭제곱을 의미한다.
h[n]에서 해시 충돌이 발생하면 h[n+1x1], h[n+2x2], h[n+3x3]과 같이 거듭제곱한 인덱스만큼 이동하고 빈 공간을 찾으면 데이터를 저장하는 방식이다.
이차 조사법은 선형 조사법보다 군집화 현상이 적지만 완전히 해결한다고 할 수는 없다.
◦
이중 해싱(double hashing)
해시 충돌이 발생하면 다른 해시 함수를 한 번 더 적용하는 방법이다.