면접카타 - [Data structure] 16~18

16. 그래프(Graph)와 트리(Tree)의 설명 및 차이점

1) 그래프(Graph)

그래프는 정점(Vertex, Node)과 간선(Edge)으로 이루어진 자료구조로, 네트워크 모델을 표현하는 데 사용됩니다. 그래프는 여러 가지 방식으로 분류될 수 있습니다.

• 방향성 여부
  • 무방향 그래프(Undirected Graph): 간선에 방향이 없으며, A - B는 B - A와 동일합니다.
  • 방향 그래프(Directed Graph, DAG): 간선에 방향이 있으며, A → B와 B → A는 다릅니다.
• 가중치 여부
  • 가중 그래프(Weighted Graph): 간선에 가중치(비용, 거리 등)가 부여됩니다.
  • 비가중 그래프(Unweighted Graph): 간선에 가중치가 없습니다.
• 순환 여부
  • 순환 그래프(Cyclic Graph): 특정 경로를 따라 다시 원래의 정점으로 돌아올 수 있습니다.
  • 비순환 그래프(Acyclic Graph, DAG): 순환이 존재하지 않습니다.

2) 트리(Tree)

트리는 사이클이 없는 방향 그래프(Directed Acyclic Graph, DAG)의 한 종류입니다. 다음과 같은 특성을 가집니다.

• 계층적 구조를 가지며, 부모-자식 관계가 존재합니다.
• 루트 노드(Root Node)가 있으며, 루트에서 모든 노드로 단일 경로가 존재해야 합니다.
• N개의 노드가 있다면 항상 N-1개의 간선을 가집니다.
• 사이클이 존재하지 않습니다.

트리의 대표적인 유형:

• 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리.
• 이진 검색 트리(Binary Search Tree, BST): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 갖는 이진 트리.
• 균형 트리(Balanced Tree): 모든 서브트리의 높이 차이가 일정 범위 내에 있는 트리.
• 힙(Heap): 부모가 자식보다 크거나(최대 힙) 작아야(최소 힙) 하는 트리 구조.

3) 그래프와 트리의 차이점

구분	그래프 (Graph)	트리 (Tree)
정의	정점(Vertex)과 간선(Edge)으로 구성된 자료구조로, 다양한 관계와 네트워크를 표현할 수 있습니다.	사이클이 없고, 모든 정점이 연결된 특수한 형태의 그래프입니다. (일반적으로 계층적 관계를 나타내기 위해 사용됨)
방향성	방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph) 모두 가능하며, 상황에 따라 적절히 선택할 수 있습니다.	기본적으로 무방향이지만, 계층적 표현(루트-자식 관계)을 위해 방향성(부모→자식)을 부여하여 표현할 수 있습니다.
순환	사이클(순환 경로)이 존재할 수 있습니다.	사이클이 없으며, 임의의 두 정점 사이에 유일한 경로가 존재합니다.
연결성	연결되어 있을 수도, 여러 개의 분리된 컴포넌트(서브그래프)를 가질 수도 있습니다.	기본적으로 연결되어 있으며, 모든 정점이 하나의 컴포넌트 내에 있습니다.
루트 노드	별도의 루트 노드 개념이 없으며, 시작점은 상황에 따라 임의로 선택할 수 있습니다.	유일한 루트 노드가 존재하며, 이를 기준으로 계층적(트리 구조) 관계가 정의됩니다.
간선 수	무방향 그래프 : ∣V∣(∣V∣−1)|  / 2 방향 그래프 : ∣V∣(∣V∣−1)	V
구조	복잡한 네트워크, 그래프 탐색, 최단 경로 등 다양한 문제를 해결하기 위해 사용됩니다.	계층적 구조를 표현하며, 부모-자식 관계를 기반으로 한 데이터 구조(예: 파일 시스템, 조직도, 이진 트리 등)로 많이 활용됩니다.

---

꼬리 질문

16-1. 그래프의 탐색 알고리즘에는 어떤 것이 있으며, 각각의 차이점은 무엇인가요?

그래프 탐색 알고리즘은 크게 너비 우선 탐색(BFS, Breadth-First Search과 깊이 우선 탐색(DFS, Depth-First Search)으로 나뉩니다. 두 알고리즘은 그래프의 구조를 탐색하는 방식에서 차이가 있습니다.

---

1) 너비 우선 탐색 (BFS, Breadth-First Search)

BFS는 큐(Queue) 자료구조를 사용하여, 최단 경로 탐색 및 네트워크 연결 탐색 등에 사용됩니다.
동작 방식

1. 시작 노드를 큐에 삽입하고 방문 표시
2. 큐에서 노드를 꺼내 해당 노드와 연결된 미방문 노드를 모두 큐에 삽입
3. 위 과정을 큐가 빌 때까지 반복

시간 복잡도: O(V+E)O(V + E) (V: 정점 수, E: 간선 수)
공간 복잡도: O(V)O(V) (최악의 경우 모든 노드를 큐에 저장)

✅ 장점

• 최단 경로(가중치 없는 그래프) 탐색 가능
• 가까운 노드부터 탐색하여 특정 조건을 만족하는 경로를 빠르게 찾을 수 있음

❌ 단점

• 큐를 사용하므로 메모리 사용량이 많음 (특히 노드가 많을 경우)

---

2) 깊이 우선 탐색 (DFS, Depth-First Search)

DFS는 스택(Stack) 또는 재귀(Recursion)를 이용하여 경로 탐색, 순환 검출, 위상 정렬 등에 사용됩니다.
동작 방식

1. 시작 노드를 스택에 삽입하고 방문 표시
2. 스택의 가장 위에 있는 노드를 꺼내고, 미방문 인접 노드를 스택에 삽입
3. 더 이상 갈 곳이 없으면 백트래킹(Backtracking)
4. 위 과정을 스택이 빌 때까지 반복

시간 복잡도: O(V+E)O(V + E)
공간 복잡도: O(V)O(V) (재귀 호출 시 스택 크기)

✅ 장점

• 메모리 사용량이 BFS보다 적음
• 목표 노드가 깊은 곳에 있을 경우 빠르게 찾을 수 있음

❌ 단점

• 최단 경로를 보장하지 않음
• 재귀 호출을 사용할 경우, 너무 깊어지면 스택 오버플로우 가능

---

3) BFS vs DFS 비교

알고리즘	BFS  (너비 우선 탐색)	DFS (깊이 우선 탐색)
자료구조	큐 (Queue)	스택(Stack) 또는 재귀
최단 경로 보장	O (가중치 없는 그래프에서)	X
공간 복잡도	높음 (많은 노드를 저장)	낮음 (재귀 깊이만큼 사용)
순환 탐지	가능	가능
적용 예시	최단 경로 탐색, 네트워크	퍼즐 문제, 위상 정렬

 

---

16-2. 트리에서 균형을 유지하는 기법에는 어떤 것들이 있으며, 각각의 장점과 단점은 무엇인가요?

트리가 한쪽으로 치우치면 검색, 삽입, 삭제 연산의 시간 복잡도가 O(N)O(N)까지 증가할 수 있습니다. 이를 방지하기 위해 균형 유지 기법이 사용됩니다.

---

1) AVL 트리 (Adelson-Velsky and Landis Tree)

AVL 트리는 각 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 1 이하가 되도록 유지하는 자기 균형 이진 검색 트리입니다.

• 불균형 발생 시 회전(Rotation)을 수행하여 균형 유지
• 회전 연산이 자주 발생하므로 삽입 및 삭제가 다소 느릴 수 있음

✅ 장점

• 검색 성능이 항상 O(log⁡N)O(\log N)을 유지
• 트리가 심하게 치우치는 경우가 없음

❌ 단점

• 삽입/삭제 시 회전 연산이 발생하여 비용이 증가 (O(log⁡N)O(\log N))

---

2) Red-Black 트리 (적흑 트리)

Red-Black 트리는 노드에 색깔(빨강, 검정)을 부여하여 균형을 유지하는 이진 검색 트리입니다.

• 균형을 완벽히 유지하는 대신, 어느 정도의 불균형은 허용
• 평균적인 성능이 우수하며 데이터베이스, OS 커널에서 많이 사용

✅ 장점

• 균형을 유지하면서도 삽입/삭제 연산이 AVL 트리보다 빠름
• 최악의 경우에도 검색, 삽입, 삭제 연산이 O(log⁡N)O(\log N)

❌ 단점

• AVL 트리보다 검색 성능이 약간 낮음 (균형성이 완벽하지 않음)

---

3) B-Tree 및 B+ Tree

B-Tree는 데이터베이스 및 파일 시스템에서 많이 사용되는 균형 트리입니다.

• 한 개의 노드가 여러 개의 자식을 가질 수 있음
• 디스크 I/O를 줄이기 위해 설계됨

✅ 장점

• 대량의 데이터를 효율적으로 저장 가능
• 검색 및 삽입/삭제 연산이 모두 O(log⁡N)O(\log N)

❌ 단점

• 단순한 BST에 비해 구조가 복잡함

---

균형 트리 비교

트리 종류	검색 속도	삽입/삭제 속도	회전 연산 발생 빈도	사용 사례
AVL 트리	빠름	느림 (자주 회전)	높음	검색 최적화
Red-Black 트리	보통	빠름	적음	일반적인 균형 유지
B-Tree	빠름	빠름	없음	데이터베이스, 파일 시스템

 

---

17. 이진 트리(Binary Tree), 이진 검색 트리(Binary Search Tree), 힙(Heap) 설명 및 차이점

1) 이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 일반적인 형태의 트리이며, 특정한 정렬 규칙은 없습니다.

종류

• 포화 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식을 가짐.
• 완전 이진 트리(Complete Binary Tree): 왼쪽부터 차례대로 채워진 트리.
• 균형 이진 트리(Balanced Binary Tree): 왼쪽과 오른쪽 서브트리의 높이가 비슷한 트리.

---

2) 이진 검색 트리 (Binary Search Tree, BST)

이진 검색 트리는 이진 트리의 한 종류로, 다음 조건을 만족합니다.

1. 왼쪽 서브트리의 모든 노드는 부모보다 작음.
2. 오른쪽 서브트리의 모든 노드는 부모보다 큼.
3. 이러한 규칙이 모든 서브트리에 대해 재귀적으로 적용됨.

장점

• 이진 탐색이 가능하여 평균 시간 복잡도가 O(log⁡N)O(\log N)
• 정렬된 상태로 데이터를 저장할 수 있음

단점

• 한쪽으로 치우친 경우(편향 트리) 성능이 O(N)O(N)까지 저하됨 → 이를 해결하기 위해 균형 트리(AVL, Red-Black Tree) 사용.

---

3) 힙 (Heap)

힙은 완전 이진 트리(Complete Binary Tree)를 기반으로 하며, 다음 두 가지 성질을 가집니다.

1. 최대 힙(Max Heap): 부모 노드의 값이 항상 자식보다 크거나 같음.
2. 최소 힙(Min Heap): 부모 노드의 값이 항상 자식보다 작거나 같음.

특징

• 삽입, 삭제 연산이 O(log⁡N)O(\log N)
• 우선순위 큐(Priority Queue) 구현에 사용됨

---

추가적인 자료구조

Binary Heap

이진 힙은 완전 이진 트리 기반의 힙으로, 우선순위 큐에서 많이 사용됩니다.

• 시간 복잡도: 삽입/삭제 O(log⁡N)O(\log N), 최댓값/최솟값 접근 O(1)O(1)

Red-Black Tree (적흑 트리)

이진 검색 트리의 일종으로, 균형을 유지하기 위해 추가적인 규칙을 적용한 트리입니다.

• 모든 경로에서 검은색 노드 수가 동일해야 균형 유지됨.
• 삽입/삭제 시 O(log⁡N)O(\log N)을 보장.

B+ Tree

데이터베이스(DB)에서 많이 사용되는 균형 트리 구조로,

• 모든 데이터를 리프 노드에 저장하여 검색 성능을 높임.
• 디스크 I/O 최소화를 위해 설계됨.

---

꼬리 질문

17-1. 이진 검색 트리가 편향될 경우 어떤 문제가 발생하며, 어떻게 해결할 수 있나요?

1) 이진 검색 트리가 편향될 경우 발생하는 문제

이진 검색 트리(BST, Binary Search Tree)는 일반적으로 검색, 삽입, 삭제 연산이 O(log⁡N)O(\log N)의 시간 복잡도를 가지지만, 편향된 트리(Skewed Tree)가 될 경우 성능이 크게 저하됩니다.

✅ 편향 트리(Skewed Tree)란?
트리가 한쪽 방향으로 치우쳐서 균형이 맞지 않는 경우를 말합니다.

• 왼쪽 편향 트리 (Left-Skewed Tree): 모든 노드가 왼쪽 자식만 가짐
• 오른쪽 편향 트리 (Right-Skewed Tree): 모든 노드가 오른쪽 자식만 가짐

🚨 문제점:

• 검색 연산이 선형 탐색(Linked List와 동일)과 다를 바 없어짐
• 삽입/삭제 연산 시에도 최악의 경우 O(N)O(N) 시간 복잡도 발생

---

2) 해결 방법

이진 검색 트리가 편향되는 문제를 해결하려면 균형을 유지하는 트리(Balanced Tree)를 사용해야 합니다.

✅ 해결 방법 1: AVL 트리 (AVL Tree) 사용

• 노드 간 높이 균형 조건(Height Balance Property)을 유지
• 균형이 깨질 경우, 회전(Rotation) 연산을 통해 재조정

🔹 장점: 검색 성능이 안정적이며 O(log⁡N)O(\log N) 유지
🔹 단점: 삽입/삭제 연산 시 균형을 맞추는 비용이 발생 (회전 연산이 많음)

---

✅ 해결 방법 2: Red-Black 트리 (Red-Black Tree) 사용

• AVL 트리보다 균형을 덜 유지하지만, 삽입/삭제 연산의 효율성이 좋음
• 회전 연산이 적어 AVL보다 성능이 나은 경우가 많음

🔹 장점: 검색/삽입/삭제 모두 O(log⁡N)O(\log N) 유지, 회전 비용이 낮음
🔹 단점: AVL보다 검색 속도가 조금 느림

---

✅ 해결 방법 3: B-Tree / B+ Tree 사용 (데이터베이스, 파일 시스템용)

• 다중 자식을 가지는 균형 트리(Balanced Tree)
• 대량의 데이터 처리에 적합, 데이터베이스 및 파일 시스템에서 많이 사용됨

🔹 장점: 디스크 접근 최적화, 다량의 데이터를 효과적으로 관리 가능
🔹 단점: 구조가 복잡하여 구현이 어려움

---

17-2. Red-Black Tree와 AVL Tree의 차이점은 무엇인가요?

구분 Red-Black Tree AVL Tree

균형 유지 방식	균형을 덜 엄격하게 유지	균형을 엄격하게 유지
균형 조건	흑-적 노드 규칙을 따름	왼쪽/오른쪽 서브트리 높이 차이 최대 1
검색 속도	평균적으로 O(log⁡N)O(\log N)	항상 O(log⁡N)O(\log N) 유지
삽입/삭제 속도	더 빠름 (회전 적음)	더 느림 (회전 많음)
사용 사례	일반적인 트리 균형 유지 (ex: STL map, set)	검색이 중요한 경우 (ex: DB 인덱싱)

✅ 요약

• 검색이 많다면 AVL Tree가 유리
• 삽입/삭제가 많다면 Red-Black Tree가 유리

---

18. 해시 테이블(Hash Table)과 이진 검색 트리(Binary Search Tree, BST) 비교

1) 해시 테이블 (Hash Table)

해시 테이블은 키(Key)를 해시 함수(Hash Function)를 통해 해시 값(Hash Value)으로 변환하여 데이터를 저장하는 자료구조입니다.

• 시간 복잡도: 평균 O(1)O(1) (최악 O(N)O(N), 해시 충돌 발생 시)
• 충돌 해결 방식: 체이닝(Chaining), 개방 주소법(Open Addressing)

2) 이진 검색 트리 (BST)

이진 검색 트리는 정렬된 데이터를 효율적으로 탐색할 수 있는 트리 구조입니다.

• 시간 복잡도: 평균 O(log⁡N)O(\log N), 최악 O(N)O(N) (편향 트리)

3) 비교

기준	해시 테이블	이진 검색 트리
검색 속도	평균 O(1)O(1), 최악 O(N)O(N)	평균 O(log⁡N)O(\log N), 최악 O(N)O(N)
정렬	X (정렬 불가능)	O (정렬 가능)
메모리 사용	추가적인 해시 버킷 필요	노드 포인터 저장 필요

---

꼬리 질문

18-1. 해시 충돌을 해결하는 방법에는 어떤 것들이 있나요?

해시 테이블에서 두 개 이상의 키가 같은 해시 값(Hash Value)을 가질 때 이를 해시 충돌(Hash Collision)이라고 합니다. 이를 해결하기 위해 여러 가지 방법이 존재합니다.

---

1) 개방 주소법 (Open Addressing)

충돌이 발생하면 빈 공간을 찾아 데이터를 저장하는 방식입니다.

• 선형 탐사(Linear Probing): 충돌 발생 시, 다음 빈 슬롯을 찾음
• 이차 탐사(Quadratic Probing): 충돌 발생 시, 일정한 제곱 간격으로 이동
• 이중 해싱(Double Hashing): 2개의 해시 함수를 이용하여 충돌 방지

✅ 장점: 추가적인 데이터 구조가 필요 없음
❌ 단점: 클러스터링(연속된 빈 슬롯 부족) 문제 발생

---

2) 체이닝 (Chaining)

각 해시 슬롯에 연결 리스트(Linked List) 또는 트리(Tree)를 사용하여 충돌을 해결

• 동일한 해시 값에 여러 개의 데이터를 저장 가능

✅ 장점: 충돌이 많아도 성능 저하가 적음
❌ 단점: 메모리 사용량 증가

---

3) 해시 함수 개선

충돌이 발생하지 않도록 더 좋은 해시 함수를 사용하여 해결

• 이상적인 해시 함수는 모든 키에 대해 고유한 값을 반환하지만, 현실적으로 불가능
• SHA-256, MurmurHash 같은 해시 함수를 활용하여 충돌을 줄일 수 있음

---

18-2. 데이터가 정렬되어 있어야 하는 경우, 해시 테이블과 BST 중 어떤 것을 선택해야 하나요?

✅ 정렬이 필요한 경우, BST를 선택하는 것이 더 적합합니다.
해시 테이블(Hash Table)은 키-값 매핑에는 뛰어나지만, 데이터 정렬이 필요할 경우 적합하지 않습니다.

 

해시 테이블 vs BST 비교

구분	해시 테이블	이진 검색 트리 (BST)
검색 속도	평균 O(1)O(1)	O(log⁡N)O(\log N)
삽입/삭제 속도	O(1)O(1)	O(log⁡N)O(\log N)
정렬 지원	❌ (지원하지 않음)	✅ (항상 정렬 상태 유지)
순차 탐색	❌ (비효율적)	✅ (중위 순회로 정렬된 결과 얻음)
충돌 가능성	✅ (충돌 가능)	❌ (없음)

✅ BST를 선택하는 경우

• 데이터를 오름차순/내림차순으로 유지해야 할 경우
• 범위 검색(range query)이 필요한 경우 (예: "A~C로 시작하는 데이터 찾기")

✅ 해시 테이블을 선택하는 경우

• 키를 기반으로 빠른 조회가 필요할 경우
• 정렬이 필요하지 않은 단순한 데이터 저장 및 검색