기술 면접 - 자료 구조(비선형 구조)

1. 트리

---

• 트리는 계층적 관계를 표현하는 자료 구조
• 연결리스트를 기반으로 만들어진다

• 노드
  • 트리의 구성요소에 해당하는 1, 3, 6 같은 요소
• 간선
  • 노드와 노드를 연결하는 선
• 루트 노드
  • 트리 구조에서 최상위에 존재하는 노드
• 리프 노드
  • 자식 노드가 없는 노드
• 내부 노드
  • 리프 노드를 제외한 모든 노드

이진 트리와 서브 트리

루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다. 위의 그림이 이진 트리의 예시!

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level(레벨)이라고 한다. 레벨의 값은 0 부터 시작하고 따라서 루트 노드의 레벨은 0 이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.

Perfect Binary Tree (포화 이진 트리), Complete Binary Tree (완전 이진 트리)

모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 한다. 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다. 배열로 구성된 Binary Tree는 노드의 개수가 n 개이고 root가 0이 아닌 1에서 시작할 때, i 번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.

이진 트리의 순회

• 전위 순회
  • 루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리
• 중위 순회
  • 왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리
• 후위 순회
  • 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 노드
• 재귀적으로 구현하면 쉽게 할 수 있다.

2. 우선순위 큐와 힙

---

우선순위 큐

• 이름만 봐서는 큐와 비슷할 것 같지만 사실 많은 차이가 있음
• 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

구현 방법

• 배열 기반
• 연결리스트 기반
• 힙 기반

힙

• 힙은 완전 이진 트리
• 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 함, 즉 루트 노드에 저장된 값이 가장 커야함(최대 힙)
• 루트노드에 저장된 값이 가장 작다면 최소 힙

• 이렇게 힙은 루트 노드에 우선순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조
  • 우선순위 큐를 만들기 쉽겠다!!

3. 그래프

---

Graph

• 정점과 간선의 집합

그래프 관련 용어 정리

무향 그래프와 방향 그래프

말 그대로 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph 라 하고, 간선에 방향성이 포함되어 있는 그래프를 Directed Graph 라고 한다.

Degree

Undirected Graph 에서 각 정점(Vertex)에 연결된 Edge 의 개수를 Degree 라 한다. Directed Graph 에서는 간선에 방향성이 존재하기 때문에 Degree 가 두 개로 나뉘게 된다. 각 정점으로부터 나가는 간선의 개수를 Outdegree 라 하고, 들어오는 간선의 개수를 Indegree 라 한다.

가중치 그래프(Weight Graph)와 부분 그래프(Sub Graph)

가중치 그래프란 간선에 가중치 정보를 두어서 구성한 그래프를 말한다. 반대의 개념인 비가중치 그래프 즉, 모든 간선의 가중치가 동일한 그래프도 물론 존재한다. 부분 집합과 유사한 개념으로 부분 그래프라는 것이 있다. 부분 그래프는 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프를 말한다.

그래프를 구현하는 두 방법

인접 행렬 (adjacent matrix) : 정방 행렬을 사용하는 방법

해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1) 으로 파악할 수 있다. Edge 개수와는 무관하게 V^2 의 Space Complexity 를 갖는다.

인접 리스트 (adjacent list) : 연결 리스트를 사용하는 방법

vertex 의 adjacent list 를 확인해봐야 하므로 vertex 간 연결되어있는지 확인하는데 오래 걸린다. Space Complexity 는 O(E + V)이다.

그래프 탐색

깊이 우선 탐색 (Depth First Search: DFS)

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다. 어떤 자료구조를 사용해야할까? 바로 Stack 이다.

Time Complexity : O(V+E) … vertex 개수 + edge 개수

너비 우선 탐색 (Breadth First Search: BFS)

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. BFS 에서는 자료구조로 Queue 를 사용한다. 연락을 취할 정점의 순서를 기록하기 위한 것이다. 우선, 탐색을 시작하는 정점을 Queue 에 넣는다.(enqueue) 그리고 dequeue 를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다. 즉 vertex 들을 방문한 순서대로 queue 에 저장하는 방법을 사용하는 것이다.

Time Complexity : O(V+E) … vertex 개수 + edge 개수 BFS 로 구한 경로는 최단 경로이다.