[Data Structure/자료구조] 힙, 트리, 그래프(Heap, Tree, Graph)

힙 Heap

힙에 대해 설명하고, Heap Sort에 대해 설명해 주세요.

• 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조이다.
• 우선순위 큐를 위해서 만들어졌다.
• 각 노드의 키값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키값보다 크지 않은(최소힙) 완전이진트리 입니다. 
• 우선 순위 큐 란, 우선순위의 개념을 큐에 도입한 자료구조 -> 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져 나간다.
• Heap Sort 공간복잡도:

 

힙을 배열로 구현한다고 가정하면, 어떻게 값을 저장할 수 있을까요?

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 배열로 구현한다고 할 때 root 노드를 0번째에 저장하고 그다음부터 자식 노드를 저장하면,
  왼쪽 1번 오른쪽 2번,
  그 밑에 왼쪾의 자식을 3, 4 오른쪽의 자식을 5, 6
  ...
  이렇게 했을 때 각 노드의 인덱스를 계산하면
  왼쪽 노드의 인덱스 값은 부모노드*2,
  오른쪽 노드의 인덱스 값은 부모노드*2+1
• 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않고, 1부터 시작하며 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

 

힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.

-답변준비중-

 

힙 정렬의 시간복잡도는 어떻게 되나요?

• 힙 구조 생성시 연산 수는 힙의 높이와 동일하므로 O(log N)이 됩니다.
• 따라서 힙 정렬의 전체 시간 복잡도는 힙 생성(Heapify)알고리즘 시간 복잡도 O(log N) * 전체 데이터 수 N = O(N * logN)입니다. 

---

트리 Tree

트리에 대해 설명해주세요

• 트리는 제약이 있는 방향 그래프의 일종이다.
• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
• 하나의 부모 정점을 가지기 때문에, 루트에서 특정 정점으로 가는 경로는 반드시 하나만 존재한다.

 

트리의 용어에 대해 설명해주세요

• root: 가장 상위의 정점
• leaf node : 더 이상 자식이 없는 정점
• level : 루트로부터 몇 번째 깊이인지 표현
• degree : 한 정점에서 뻗어나가는 정점의 수

 

트리의 종류에 대해 설명해주세요.

이진트리 Binary Tree

• 트리의 부모 노드가 최대 두 개의 자식 노드만을 가질 때 해당 트리를 이진트리라고 하며
  DFS기반 탐색 알고리즘인 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)를 적용하여 이진트리 전체 노드를 탐색할 수 있다.
• 각 정점이 최대 2개 자식을 갖는 트리이다.
• 탐색을 위한 알고리즘에 많이 쓰인다.
• 정점이 n개인 이진 트리는 최악의 경우 높이가 n이 될 수 있다. (편향 트리)
• 정점이 n개인 포화 또는 완전 이진 트리의 높이는 log n이다.
• 높이가 h인 포화 이진 트리는 2^h - 1 개의 정점을 가진다.
• 일반적인 이진 트리를 사용하는 경우는 많지 않고, 응용을 자주한다.
• 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리 등을 구현하기 위해 사용된다.

완전이진트리 Complete Binary Tree

• 마지막 레벨을 제외하고 모든 정점이 채워져 있는 트리
• 순서대로 들어가야만 완전 이진 트리라고 할 수 있다.

정이진트리 Full Binary Tree

- 답변 준비중 - 

이진탐색트리 BST (Binary Search Tree)

• 이진 탐색 트리는 말 그대로 이진 탐색에 트리의 개념이 더해진 것으로 평균 O(NlogN)로 특정 값을 탐색하는 것에 빠른 성능을 보여준다.(최악의 경우 O(N))
• 이진탐색트리는 해당 조건을 만족해야 한다.
  1) 부모 노드의 왼쪽 노드는 부모 노드보다 작아야 한다.
  2) 부모 노드의 오른쪽 노드는 부모 노드보다 커야 한다.

 

Lower Bound, Upper Bound 는 무엇이고, 이를 어떻게 구현할 수 있을까요?

• Lower Bound와 Upper Bound는 모두 경계값을 찾는 과정이다.
• 이진탐색(Binary Search)이 원하는 값을 찾는 과정 이었다면,
  Lower Bound는 원하는 값이 처음 나오는 위치를 찾는 과정이고,
  Upper Bound는 원하는 값이 나오는 마지막 위치를 찾는 과정이다.
• 구현방법:

최소 신장 트리 Minimum Spanning Tree가 무엇이고, 어떻게 구할 수 있을지 설명해 보세요.

Spanning Tree

• Spanning Tree는 그래프의 최소 연결 부분 그래프 이다.
  최소 연결 = 간선의 수가 가장 적다는 의미가 되며, n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.
  즉, 그래프에서 일부 간선을 선택해서 만든 트리
• Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
  따라서, Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다.

MST

• MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말한다.
• 즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.
• 특징: 간선의 가중치의 합이 최소여야 한다.
           n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
           사이클이 포함되어서는 안된다.
• 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우에 MST가 사용된다.

Kruskal

• 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
• 간선 선택을 기반으로 하는 알고리즘이다.
• 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.

Prim

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법이다.
• 정점 선택을 기반으로 하는 알고리즘이다.
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.
•  

---

그래프 Graph

그래프란?

• 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다.
• 인물 관계도, 지하철 노선도, 페이지 랭크(검색 알고리즘)에 활용될 수 있다.
• 그래프는 사이클이 발생할 수 있으므로 탐색 시에 무한 루프에 빠지지 않도록 사이클을 찾아야 할 필요가 있다.

 

그래프의 종류

1.방향성에 따른 분류

무방향그래프

• 간선의 방향이 존재하지 않는다.
• 하나의 간선으로 양방향으로 이동이 가능하다.

방향그래프

• 간선에 방향성이 존재한다.
• 양방향으로 이동할 수 있더라도 a-b와 b-a는 다른 간선으로 취급된다.
• 일방통행이 가능하다.

2.연결상태에 따른 분류

연결그래프

• 모든 정점이 서로 이동 가능한 상태인 그래프

비연결 그래프

• 특정 정점 쌍 사이에 간선이 존재하지 않는 그래프

완전 그래프

• 모든 정점이 연결된 상태인 그래프

 

Graph 용어정리

• 인접: 두 정점을 연결하는 간선이 있을 때 서로 인접하다고 한다
• 부속: 인접한 두 정점 사이의 간선은 두 정점에 부속되었다고 한다
• 차수: 정점에 부속되어 있는 간선의 수
• 경로: 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것
• 경로 길이: 경로를 구성하는 간선의 수
• 단순 경로: 모두 다른 정점으로 구성된 경로
• 사이클: 단순 경로 중에서 경로의 시작 정점과 끝 정점이 같은 경로
• 연결 그래프: 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프(한 마디로 혼자 동떨어진 정점이 없는 그래프, 반대로 단절 그래프도 존재한다.)

 

그래프를 구현하는 두 가지 방식에 대해 설명해주세요.

• 인접행렬과 인접리스트로 구현이 가능하다.

인접행렬 방식

• 인접 행렬은 그래프를 2차원 배열에 저장하는 방법이다.
  부속된 간선을 찾는 것은 빠르지만 |V| x |V| 만큼의 공간이 필요하여 저장 측면에서 비효율적입니다. (|V| : 정점 수)
  노드 수보다 간선 수가 많은 dense graph이거나 빠르게 부속(incident)된 간선을 찾을 때 주로 사용합니다.
• 각 행과 열은 정점을 나타냅니다.

인접리스트 방식

• 인접 리스트는 인접한 정점을 연결 리스트로 저장하는 방법이다.
  인접 리스트는 연결된 간선에 대한 값만 저장하기 때문에 저장 측면에서 효율적이고 간선 수보다 노드 수가 많은 spare graph에 주로 사용합니다.
• 정점은 배열로 저장하고 각 정점에 인접한 정점들은 연결 리스트로 관리합니다.

+ 두 방식의 시간복잡도, 공간복잡도 차이

• 인접행렬방식:
  • "두 정점이 연결되었는지" 확인하는 시간복잡도: O(1)
  • "한 정점에 연결된 모든 정점을 찾는" 시간복잡도: O(|V|)
  • 공간복잡도: O(|v^2|) -> 노드수 x 노드수 만큼의 행렬이 필요하기 때문
• 인접리스트방식: 
  • "두 정점이 연결되었는지" 확인하는 시간복잡도: O(d) (d=degree(i))
  • "한 정점에 연결된 모든 정점을 찾는" 시간복잡도: O(d)
  • 공간복잡도: O(|V|+|E|) -> 정점의 수만큼 공간이 필요하고 인접한 정점을 저장하기 위해 간선 수만큼의 추가 공간이 필요하기 때문

 

그래프에서, 최단거리를 구하는 방법에 대해 설명해 주세요.

• 그래프에서의 최단 경로는 그래프 사이에서 두 노드 사이의 가장 짧은 경로를 찾는 문제이다.
• 최단 경로를 구하기 위한 방법은 아래 알고리즘을 활용할 수 있다.
  • Breath First Search (BFS)
  • 다익스트라(Dijkstra)
  • 벨만-포드(Bellman-Ford)
  • 플로이드-워셜(Floyd-Warshall)

 

트리와 그래프의 차이는 무엇인가요?

• 방향: 그래프는 방향과 무방향으로 방향성을 따진다.
• 사이클: 그래프는 순환/비순환/자기순환 등으로 사이클을 나타낼 수 있다.
• 루트노드: 그래프는 루트 개념이 없지만 트리는 한 개의 루트만 존재한다.
• 부모-자식: 그래프는 부모자식의 개념이 없지만 트리는 루트를 제외하면 모두 1개의 부모노드를 가진다.

 

사이클이 없는 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요.

• 사이클이 없는 그래프가 항상 트리인것은 아니다.
• 두 개의 연결된 부분 그래프가 있는 경우 사이클이 없지만 트리가 아닙니다. 왜냐하면 연결된 부분 그래프 각각이 트리이지만 전체 그래프는 두 개의 트리가 연결된 형태이기 때문입니다.
• -> 여러개의 연결된 부분 그래프로 이루어진 그래프는 트리가 아니다