🔀비선형 자료 구조

비선형 자료구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말합니다. 일반적으로 트리나 그래프를 말합니다.

🔗 그래프

그래프는 정점과 간선으로 이루어진 자료 구조를 말합니다.

🧭 정점과 간선

어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 '어떠한 곳'은 정점(vertex)이 되고 '무언가'는 간선(edge)이 됩니다.

단방향 간선과 양방향 간선이 있습니다.

정점으로 나가는 간선을 정점의 outdegree라고 하며, 들어오는 간선을 해당 정점의 indegree라고 합니다. 앞 그림의 정점 V는 outdegree는 세 개, indegree는 두 개인 상태입니다. 또한, 정점은 약자로 V 또는 U라고 하며, 보통 어떤 정점으로부터 시작해서 어떤 정점까지 간다를 "U에서부터 V로 간다."라고 표현합니다. 지금까지 설명한 정점과 간선으로 이루어진 집합을 '그래프(graph)'라고 합니다.

 

용어 설명: 

• 가중치:
  간선과 정점 사이에 드는 비용을 뜻합니다. 1번 노드와 2번 노드까지 가는 비용이 한 칸이라면 1번 노드에서 2번 노드까지의 가중치는 한 칸입니다.

---

🌳 트리

그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합입니다. 루트 노드, 내부 노드, 리프 노드 등으로 구성됩니다. 참고로 트리로 이루어진 집합을 숲이라고 합니다.

📐 트리의 특징

1. 부모, 자식 계층 구조를 가집니다. 같은 경로상에서 어떤 노느보다 위에 있으면 부모, 아래에 있으면 자식 노드가 됩니다.
2. V-1 = E 라는 특징이 있습니다. 간선 수는 노드 수 -1입니다.
3. 임의의 두 노드 사이의 경로는 '유일무이'하게 '존재'합니다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있습니다. 

🌱 트리의 구성

 루트 노드, 내부 노드, 리프 노드로 이루어져 있습니다.

🌲 루트 노드

가장 위에 있는 노드를 뜻합니다. 보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많습니다.

🌿 내부 노드

루프 노드와 리프 노드 사이에 있는 노드를 뜻합니다.

🍃 리프 노드

리프 노드는 자식 노드가 없는 노드를 뜻합니다.

 

트리의 높이와 레벨: 

• 깊이:
  트리에서의 깊이는 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 말합니다.
• 높이:
  트리의 높이는 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리를 의미합니다.
• 레벨:
  트리의 레벨은 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미를 지닙니다. 1번 노드를 0레벨이라고 하고 2번 노드, 3번 노드까지의 레벨을 1레벨이라고 할 수도 있고, 1번 노드를 1레벨이라고 한다면 2번 노드와 3번 노드는 2레벨이 됩니다.
• 서브트리:
  트리 내의 하위 집합을 서브트리라고 합니다. 트리 내에 있는 부분집합이라고도 보면 됩니다. 

🌲 이진 트리

이진 트리는 자식의 노드 수가 두 개 이하인 트리를 의미합니다.

• 정이진 트리(full binary tree):
  자식 노드가 0 또는 두 개인 이진 트리를 의미합니다.
• 완전 이진 트리(complete binary tree):
  왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벡의 경우 왼쪽부터 채워져 있습니다.
• 변질 이진 트리(degenerate binary tree):
  자식 노드가 하나밖에 없는 이진 트리를 의미합니다.
• 포화 이진 트리(perfect binary tree):
  모든 노드가 꽉 차 있는 이진 트리를 의미합니다.
• 균형 이진 트리(balanced binary tree):
  왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미합니다. map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나입니다.

🔍 이진 탐색 트리(BST)

노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리를 말합니다.

이때 왼쪽 및 오른쪽 하위 트리도 해당 특성을 가집니다. 이렇게 두면 '검색'을 하기에 용이합니다. 왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져 있기 때문에 10을 찾으려고 한다면 25의 왼쪽 노드들만 찾으며녀 된다는 것은 자명합니다. 보통 요소를 찾을 때 이진 탐색 트리의 경우 O(logn)이 걸립니다. 하지만 최악의 경우 O(n)이 걸립니다. 그 이유는 이진 탐색 트리난 삽입 순서에 따라 선형적일 수 있기 때문입니다.

⚖️ AVL 트리(Adelson-Velsky and Landis tree)

앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리입니다. 두 자식 서브트리의 높이는 항상 최대 1만큼 파이 난다는 특징이 있습니다.

이진 탐색 트리는 선형적인 트리 형태를 가질 때 최악의 경우 O(n)의 시간 복잡도를 가집니다. "이러한 최악의 경우를 배제하고 항상 균형 잡힌 트리로 만들자."라는 개념을 가진 트리가 바로 AVL 트리입니다. 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이며 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시켜가며 균형을 잡습니다.

🔴⚫ 레드 블랙 트리

균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)입니다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용됩니다. C++ STL의 set, multiset, map, and multimap이 이 레드 블랙 트리를 이용하여 구현되어 있습니다.

참고로 "모든 리프 노드와 루프 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다." 드으이 규칙을 기반으로 균형을 잡는 트리입니다.

---

🧱 힙(Heap)

완전 이진 트리 기반의 자료 구조이며, 최소힘과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 말합니다.

• 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 합니다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 합니다.
• 최소힙 : 루프 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 합니다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 합니다.

힙에는 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있습니다.

⬆️ 최대힙의 삽입

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입합니다. 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 합의 성질을 만족시킵니다.

예를 들어 8이라는 값을 가진 노드 밑에 15라는 값을 가진 노드를 삽입한다고 하면, 이 노드가 점차 올라가면서 해당 노드 위에 있는 노드와 스왑하는 과정을 거쳐 최대힙 조건을 만족하게 됩니다.

⬇️ 최대힙의 삭제

최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또다시 스왑 등의 과정을 거쳐 재구성됩니다.

---

🚦 우선순위 큐(Priority Queue)

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

우선순위 큐는 힙을 기반으로 구현됩니다.

greater를 써서 오름차순, less를 써서 내림차순으로 바꿀 수 있씁니다. int뿐만 아니라 다른 자료 구조를 넣어서 할 수도 있습니다.

참고로 C++에서 enqueue()는 push(), dequeue()는 pop()으로 구현되었습니다.

#include <bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int, greater<int>>pq; //오름차순

//priority_queue<int,vector<int>, less<int>>pq; //내림차순
int main(){
	pq.push(5);
    pq.push(4);
    pq.push(3);
    pq.push(2);
    pq.push(1);
    cout<<pq.top()<<"\n";
    return 0;
}
/*
1
*/

오름차순으로 정렬하게 했고 5,4,3,2,1이 입력되었음에도 우선순위가 높은 1이 출력되는 것을 볼 수 있습니다.

 

---

🗺️ 맵(map)

특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조입니다. 예를 들어 "이승철":1, "박동영":2 같은 방식으로 string:int 형태로 값을 할당해야 할 때 있죠? 그럴 때 map을 씁니다. 레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬됩니다.

맵을 쓸 때는 map<string, int> 형태로 구현합니다. 배열과 비슷하게 clear() 함수로 맵에 있는 모든 요소를 삭제할 수 있으며, size()로 map 크기를 구할 수 있습니다. 또한, erase()로 해당 키와 키에 매핑된 값을 지울 수 있습니다.

참고로 map은 해시 테이블을 구현할 때 쓰며 정렬을 보장하지 않는 unordered_map과 정렬을 보장하는 map 두 가지가 있습니다.

#include <bits/stdc++.h>
using namespace std;
int v[10];
int main(){
	unordered_map<string,int>umap;
    umap.insert({"test1",1});
    umap.emplace("test5",5);
    umap["test1"]=4;
    
    for(auto element:umap){
    	cout<<element.first<<"::"<<element.second<<'\n';
    }
    //map의 find 메서드는 찾지 못하면 end() 이터레이터를 반환한다.
    auto search=umap.find("test4");
    if(search!=umap.end()){
    	cout<<"found:"<<search->first<<" "<<(*search).second<<'\n\;
    }else{
    	cout<<"not found.."<<'\n';
    }
    umap["test1"]++;
    cout<<umap["test1"]<<"\n";
    
    cout<<umap.size()<<"\n";
    umap.erase("test1");
    cout<<umap.size()<<"\n";
    return 0;
 }
 /*
 test5::5
 test1::4
 not found..
 5
 2
 1
 */

map을 순회할 때는 키에 해당하는 값(key)을 first, 키에 매핑된 값(value)에 해당하는 값을 second로 탐색 가능합니다.

#include <bits/stdc++.h>
using namspace std;
int main(){
	map<string,int> _map;
    _map["큰돌"]++;
    _map["큰돌"]++;
    for(auto c:_map){
    	cout<<c.first<<":"<<c.second<<"\n";
    }
    return 0;
}
/*
큰돌 : 2
*/

---

🎯 셋(set)

특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 오로지 희소한(unique) 값만 저장하는 자료 구조입니다.

#include <bits/stdc++.h>
using namespace std;
int main(){
	set<pair<string,int>> _set;
    _set.insert({"test",1});
    _set.insert({"test",1});
    _set.insert({"test",1});
    _set.insert({"test",1});
    cout<<_set.size()<<"\n";
    return 0;
 }
 /*
 1
 */

여기서 pair는 두 가지 형을 담을 수 있는 구조이며 first, second로 그 인자에 접근이 가능합니다. 이렇게 똑같은 값을 넣었더니 1이 나오는 것을 볼 수 있습니다. 나머지 사항은 map과 비슷합니다.

오름차순으로 정렬하게 했고 5,4,3,2,1이 입력되었음에도 우선순위가 높은 1이 출력되는 것을 볼 수 있습니다.

 

---

🧩 해시 테이블

무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블입니다. 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지며 unordered_map으로 구현합니다.

---

1. 해시 테이블에 대해 설명하세요.

해시 테이블은 키와 값을 한 쌍으로 저장하는 자료구조로, 해시 함수를 사용해 키를 고유한 인덱스로 변환한 뒤 해당 위치에 값을 저장하고 조회합니다. 이를 통해 평균적으로 O(1)의 빠른 검색 성능을 제공하지만, 서로 다른 키가 같은 인덱스를 가지는 충돌이 발생할 수 있어 체이닝이나 개방 주소법과 같은 방법으로 이를 처리합니다.

 

2. 그래프와 트리의 차이점에 대해 설명하세요.

그래프는 정점과 간선으로 이루어진 일반적인 자료구조로, 사이클이 존재할 수 있고 하나의 노드가 여러 노드와 자유롭게 연결될 수 있습니다. 반면 트리는 그래프의 한 종류로, 사이클이 존재하지 않으며 루트 노드를 기준으로 부모-자식 관계가 명확하고 모든 노드가 하나의 경로로 연결된 계층 구조를 가집니다.

 

3. 이진 탐색 트리는 어떤 문제점이 있고 이를 해결하기 위한 트리 중 한 가지를 설명해보세요.

이진 탐색 트리는 데이터가 한쪽으로 치우쳐 삽입될 경우 트리의 균형이 깨져 연결 리스트와 같은 형태가 되며, 이로 인해 탐색·삽입·삭제의 시간 복잡도가 O(n)으로 성능이 저하되는 문제가 있습니다. 이를 해결하기 위해 사용되는 트리 중 하나가 AVL 트리로, 삽입과 삭제 시마다 트리의 높이 차이를 검사하고 회전을 통해 균형을 유지하여 항상 O(log n)의 성능을 보장합니다.