[기술면접] 자료구조 - 2/2

1편에 이어서 작성해 보겠습니다. 

 

 

😎 해시 테이블(Hash Table)과 시간 복잡도에 대해 설명해주세요.

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다.

빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문입니다.
각 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도로 데이터를 조회합니다. 하지만 index값이 충돌이 발생한 경우 Chanining에 연결된 리스트들까지 검색해야 하므로 O(N)까지 증가할 수 있습니다.

▶ 결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌 나는 현상이 발생하는데도 해시 테이블을 사용하는 이유는 무엇인가요?

적은 자원으로 많은 데이터를 효율적으로 관리하기 위함입니다. 

하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해집니다.

• 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능해짐
• 해시테이블의 시간복잡도 O(1) - (이진탐색트리는 O(logN))

▶ 충돌 문제를 해결하는 다양한 방법에 대해 말씀해 주세요.

1. 체이닝 : 연결리스트로 노드를 계속 추가해 나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)
2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어 있으면 다음 주소에 저장)
3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
4. 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

😎 Hash Map과 Hash Table의 차이점에 대해 설명해 주세요.

Hash Map과 Hash Table은 둘 다 키-값(key-value) 쌍의 데이터를 저장하고 검색하는 자료구조입니다. 그러나 두 자료구조 사이에는 동기화 지원 여부와 null 값 허용 여부의 차이가 있습니다.

• 해시 테이블(Hash Table)
  • 병렬 처리를 할 때 (동기화를 고려해야 하는 상황) Thread-safe 하다. =  동기화된 자료구조
    • 이는 동기화 오버헤드로 인해 Hash Map보다 성능이 떨어질 수 있습니다.
  •  null 키나 null 값이 아닌 경우에만 동작
• 해시 맵(Hash Map)
  •  일반적으로 동기화되지 않은(non-synchronized) 자료구조로, 멀티스레드 환경에서 사용할 때 안전하지 않습니다. (Thread-safe 하지 않는다.)
    • 그러나 이를 보완하기 위해 동기화(synchronized)된 Hash Map도 있습니다.
  • null 키와 null 값 모두 허용
  • 일반적으로 Hash Table보다 더 나은 성능을 제공합니다
    • Hash Map은 링크드 리스트와 트리 구조를 사용하여 충돌을 처리하고, 이를 최소화하기 위해 일반적으로 크기를 유지하기 위해 rehashing을 수행합니다. 반면, Hash Table은 단일 링크드 리스트를 사용하여 충돌을 처리합니다.

▶ 동기화된 자료구조란?

동기화된 자료구조는 멀티스레드 환경에서 안전하게 사용할 수 있는 자료구조입니다.

멀티스레드 환경에서 여러 개의 스레드가 동시에 자료구조에 접근하면 데이터 불일치(inconsistent) 문제가 발생할 수 있습니다. 이를 방지하기 위해 동기화된 자료구조를 사용합니다.

 

동기화된 자료구조는 일반적으로 락(lock)이라는 동기화 기술을 사용하여 여러 스레드가 동시에 접근할 수 없도록 막습니다. 즉, 한 스레드가 자료구조에 접근 중일 때, 다른 스레드가 접근하지 못하도록 제어합니다.

 

하지만 동기화된 자료구조를 사용하면 락(lock)을 획득하고 반납하는 과정에서 오버헤드가 발생할 수 있으므로, 성능에 영향을 미칠 수 있습니다. 따라서, 가능하면 스레드 안전하지 않은(non-thread-safe) 자료구조를 사용하는 것이 좋을 수도 있습니다. 이 경우에는 스레드 간의 접근을 제어하기 위해 다른 방법을 사용해야 합니다.

 

😎 BST(Binary Search Tree, 이진탐색트리)와 Binary Tree(이진트리)에 대해 설명해 주세요.

BST는 이진트리의 일종으로, 각 노드의 왼쪽 서브트리에는 현재 노드의 값보다 작은 값을 가지는 노드들이, 오른쪽 서브트리에는 현재 노드의 값보다 큰 값을 가지는 노드들이 위치하도록 구성된 자료구조입니다. 이진 탐색(binary search) 알고리즘의 개념을 이용하여 데이터를 저장하고 검색하는 데 사용됩니다.

 

BST는 이진 탐색 + 연결리스트를 합친 자료구조입니다. 

이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입, 삭제가 불가능

연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N)

즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능합니다.

 

BST는 다음과 같은 특징을 가집니다.

• 모든 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
• 왼쪽 서브트리의 모든 노드는 현재 노드의 값보다 작습니다.
• 오른쪽 서브트리의 모든 노드는 현재 노드의 값보다 큽니다.
• 중복된 값을 가지는 노드는 허용되지 않습니다.
  • 검색 목적 자료구조인데, 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음.
• 이진탐색트리의 순회는 '중위순회(inorder)' 방식 (왼쪽 - 루트 - 오른쪽), 중위 순회로 정렬된 순서를 읽을 수 있음

시간 복잡도

데이터의 삽입, 삭제, 검색 등을 평균적으로 O(log n)

단, 편향 트리일 경우 O(N).

삽입, 검색, 삭제 시간복잡도는 트리의 Depth에 비례합니다.

 

편향된 트리(정렬된 상태 값을 트리로 만들면 한쪽으로만 뻗음)는 시간복잡도가 O(N)이므로 트리를 사용할 이유가 사라짐 → 이를 바로 잡도록 도와주는 개선된 트리가 AVL Tree, RedBlack Tree

 

 

반면, 이진트리(Binary Tree)는 모든 노드가 최대 두 개의 자식 노드를 가지는 트리 구조를 말합니다. 이진트리는 빠른 데이터 삽입, 삭제, 검색이 가능하지만, 노드의 구성에 따라 최악의 경우 O(n)의 시간 복잡도를 가질 수 있습니다.

이진 트리는 대개 정렬되지 않은(unsorted) 데이터를 저장하거나, 이진 탐색이 아닌 다른 트리 기반 알고리즘을 구현할 때 사용됩니다.

또한, 트리의 높이(height)를 최소화하여 효율적인 탐색을 할 수 있도록 균형 잡힌 트리(balanced tree)를 사용하는 경우도 있습니다. 대표적인 균형 잡힌 트리로는 AVL 트리, Red-Black 트리 등이 있습니다.

 

▶ AVL 트리와 Red-Black 트리는 무엇인가요?

AVL 트리와 Red-Black 트리는 모두 이진 탐색 트리(Binary Search Tree)의 단점인 트리의 불균형을 해결하기 위해 고안된 자료구조로 트리의 균형을 맞추어 탐색 시간을 최소화하는 데 사용됩니다. (둘 다 이진탐색트리의 일종) 탐색 시간을 O(log n)으로 유지하면서도 삽입, 삭제 연산을 효율적으로 처리할 수 있도록 개발된 자료구조입니다.

이진 탐색 트리는 탐색이나 삽입, 삭제 연산 시 평균적으로 O(log n)의 시간 복잡도를 보입니다. 그러나, 트리의 구조가 한쪽으로 치우쳐져 있거나 노드의 개수가 많아질수록, 탐색 시간이 더욱 증가할 수 있습니다. 이러한 문제를 해결하기 위해 AVL 트리와 Red-Black 트리가 개발되었습니다.

AVL 트리는 균형 잡힌 이진 탐색 트리의 대표적인 예시입니다. AVL 트리는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리를 의미합니다. 이러한 트리 구조를 유지하기 위해 삽입, 삭제 연산 시에는 회전(rotate) 연산을 이용하여 트리의 균형을 맞추어줍니다.

Red-Black 트리는 AVL 트리보다 균형을 덜 맞춘 대신, 노드의 색깔을 이용하여 트리의 균형을 유지하는 이진 탐색 트리입니다. Red-Black 트리는 모든 노드가 레드(red) 또는 블랙(black) 중 하나의 색깔을 가지도록 구성되며, 일정한 규칙에 따라 노드를 삽입, 삭제하면서 균형을 유지하며 다음과 같은 규칙을 따릅니다.

• 루트 노드는 블랙이다.
• 모든 리프 노드는 블랙이다.
• 레드 노드의 자식 노드는 모두 블랙이다.
• 어떤 노드에서 루트 노드까지 경로상에 있는 블랙 노드의 수는 모두 같다.

이러한 규칙을 통해 Red-Black 트리는 균형을 맞추면서도 AVL 트리보다 회전 연산의 발생 횟수가 적어 더욱 효율적인 탐색이 가능합니다. Red-Black 트리의 탐색 시간 또한 O(log n)을 보장합니다.

 

😎 트리에 대해 설명해 주세요.

트리는 값을 가진 노드(Node)와 이 노드들을 연결해 주는간선(Edge)으로 이루어져 있습니다.

맨 위 노드가 루트(Root) 노드이고 모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부른다.

 

트리는 몇 가지 특징이 있습니다.

• 트리에는 사이클이 존재할 수 없다. (만약 사이클이 만들어진다면, 그것은 트리가 아니고 그래프다)
• 모든 노드는 자료형으로 표현이 가능하다.
• 루트에서 한 노드로 가는 경로는 유일한 경로뿐이다.
• 노드의 개수가 N개면, 간선은 N-1개를 가진다.

 

가장 중요한 것은, 그래프와 트리의 차이가 무엇인가인데, 이는 사이클의 유무로 설명할 수 있습니다.

그래프

• 노드와 노드 간을 연결하는 간선으로 구성된 자료 구조
• 그래프는 순환 혹은 비순환 구조를 이룬다

트리

• 방향성이 존재하고 사이클은 존재하지 않는다.(비순환)
• 트리의 순회는 전위순회, 중위순회, 후위순회 3가지가 존재한다. + 레벨 순회

▶ 트리 순회방식들에 대해 설명해 주세요.

트리 순회방식 4가지가 있습니다.

출처: https://gyoogle.dev/blog/computer-science/data-structure/Tree.html

 

1. 전위 순회(pre-order)

각 루트(Root)를 순차적으로 먼저 방문하는 방식이다.

(Root → 왼쪽 자식 → 오른쪽 자식)

1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14

 

2. 중위 순회(in-order)

왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식이다.

(왼쪽 자식 → Root → 오른쪽 자식)

8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7

 

3. 후위 순회(post-order)

왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문하는 방식이다.

(왼쪽 자식 → 오른쪽 자식 → Root)

8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1

 

4. 레벨 순회(level-order)

루트(Root)부터 계층 별로 방문하는 방식이다.

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14

 

 

 

 

 

 

 

 

---

출처:

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

https://dev-coco.tistory.com/159

https://mangkyu.tistory.com/89