비선형 자료 구조

비선형 자료 구조

• 질문

  1. 해시테이블과 이진 검색트리를 비교하고 장단점을 이야기해주세요. 그리고 메모리가 제한된 모바일 기기용 주소록에 사용할 자료구조를 설계한다면 어느쪽을 쓰는것이 좋을까요?

     • 해시테이블은 키와 값으로 이루어진 쌍을 저장하는 자료구조이며, 해시 함수를 사용하여 값을 저장하거나 검색합니다. 평균적으로 상수 시간에 삽입, 삭제, 검색이 가능하지만, 최악의 경우에는 선형 시간으로 느려질 수 있습니다. 이진 검색트리는 각 노드가 키와 값으로 이루어진 트리 자료구조이며, 왼쪽 서브트리는 부모 노드의 키보다 작은 값으로, 오른쪽 서브트리는 부모 노드의 키보다 큰 값으로 이루어집니다. 평균적으로 O(log n)의 시간복잡도를 가지며, 검색 결과를 정렬된 순서로 얻을 수 있습니다.
     • 일반적으로 해시테이블보다는 이진 검색트리가 적합합니다. 이는 해시테이블이 충돌 시 해결을 위해 추가적인 메모리를 사용하기 때문입니다. 반면, 이진 검색트리는 일반적으로 추가적인 메모리를 사용하지 않으므로, 메모리가 제한된 모바일 기기에서도 적은 메모리 사용량으로 구현이 가능합니다. 또한, 모바일 기기에서는 주소록에 데이터가 추가되거나 삭제되는 경우가 많으므로 동적으로 크기를 조절할 수 있는 이진 검색트리의 장점이 더욱 부각됩니다. 따라서, 메모리가 제한된 모바일 기기용 주소록에는 이진 검색트리를 사용하는 것이 적합합니다.

  2. 해시 테이블의 충돌 해결 방법에는 어떤 것이 있고, 각각의 장단점은 무엇인가요?

     • 해시 테이블에서 충돌은 해시 함수를 사용해 계산된 인덱스에 이미 값이 존재하는 경우를 말합니다. 충돌을 해결하는 방법에는 크게 두 가지가 있습니다. 분리연결법(Separate Chaining)은 키-값 쌍을 저장해 연결 리스트를 사용하여 충돌을 해결합니다. 크기에 제한이 없으며, 충돌이 많은 경우에도 빠른 검색이 가능합니다. 단점은 포인터를 사용하므로 메모리 사용량이 많아질 수 있습니다. 개방 주소법(Open Addressing)은 빈 인덱스를 찾아 충돌을 해결합니다. 포인터를 사용하지 않아 메모리 사용량이 적습니다. 그러나 해시 테이블 크기가 작으면 충돌이 많아져 검색 시간이 길어질 수 있습니다. 또한 규칙에 따라 빈 인덱스를 찾는 과정에서 무한 루프에 빠지는 경우가 발생할 수 있습니다.

  3. List와 Set의 차이점에 대해 말씀해주세요.

     • List에는 중복되게 들어갈 수 있지만 Set은 중복이 허용이 되지 않습니다. List에 있는 데이터를 Set에 넣으면 중복이 제거됩니다. DB의 distinct연산을 하는 효과가 있습니다. 중복이 제거되기 때문에 set에 들어 있다면 고유성이 보장 됩니다. 그래서 중복에 대한 처리를 안해줘도 됩니다.
       데이터를 수집, 처리 할 때 중복된 자료들이 수집이 될 수 있습니다. 하지만 결과는 중복되지 않아야 합니다. 그러면 중복된 데이터들을 set에 넣으면 중복이 된 데이터가 있더라도 set안에 들어가면 중복이 없어지기 때문에 중복이 없다는 것이 보장이 됩니다.

  4. 트리의 부모-자식에 대한 swap을 사용하는 경우와 일어나는 과정을 설명해주세요.

     • 이진 검색 트리에서 새로운 노드를 삽입하고, 그 노드를 삽입 위치에 맞게 재조정할 때, 삭제된 노드의 위치를 대체할 새로운 노드를 찾아야 할 때에 사용됩니다.
       노드 A를 기준으로, A의 왼쪽 자식 노드 B와 오른쪽 자식 노드 C가 있을 때, B와 A의 위치를 바꿀 경우를 예시로 들겠습니다. 노드 B가 A의 왼쪽 자식이므로, B의 오른쪽 자식 D를 A의 왼쪽 자식으로 옮기고, A를 B의 오른쪽 자식으로 연결합니다. 이제 B가 A의 부모 노드가 되었으므로, B의 부모 노드를 A의 부모 노드로 바꿉니다. 즉, B의 부모 노드를 A의 부모 노드로 변경하고, A를 B의 부모 노드로 연결합니다. 이렇게 부모-자식 스왑을 통해 B와 A의 위치가 바뀌게 됩니다. 이 과정은 트리의 높이를 줄이는 데에도 활용됩니다.

  5. 우선순위 큐는 어떤 자료구조를 기반으로 하는게 효율성이 제일 좋을까요?

     1. 우선순위를 정할 수 있어야 합니다.
     2. 연결리스트를 사용하는 것이 좋다.

  6. 해시테이블과 해시맵의 차이점

     1. 해시 알고리즘을 사용한다는 게 공통점이 존재합니다. 대부분 구현체 차이입니다.
     2. 해시맵은 비동기에서 사용 가능, 키는 반드시 존재하되 값은 널이여도 된다.(반대도 가능)

비선형 자료 구조

---

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조

• 트리
• 그래프

1. 그래프(graph)

---

정점(vertext)과 간선(edge)으로 이루어진 집합

• 단방향 간선, 양방향 간선
• 정점의 outdegree : 정점으로 나가는 간선
• 정점의 indegree : 들어오는 간선
• 정점은 V 또는 U라고 한다.
• U에서부터 V로 간다 : 어떤 정점으로부터 시작해서 어떤 정점까지 간다.

가중치

: 간선과 정점 사이에 드는 비용

• 1번 노드와 2번 노드까지 가는 비용이 한 칸이라면, 1번 노드에서 2번 노드까지의 가중치는 한 칸이다.

인접 행렬: 배열로 구현

인접 리스트: 연결리스트로 구현

2. 트리

---

정점과 간선으로 이루어져 있으며, 트리 구조로 배열된 일종의 계층적 데이터의 집합

• 구성 : 루트 노드, 내부 노드, 리프 노드 등
• 숲 : 트리로 이루어진 집합

특징

1. 부모, 자식 계층 구조를 가진다. 같은 경로상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식 노드가 된다.
2. V - 1 = E (간선 수 = 노드 수 - 1)
3. 임의의 두 노드 사이의 경로는 유일무이 하게 존재 한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.

구성

• 루트 노드 :가장 위에 있는 노드
  • 보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다.
• 내부 노드 : 루트 노드와 내부 노드 사이에 있는 노드
• 리프 노드 : 자식 노드가 없는 노드

트리의 높이와 레벨

• 깊이 : 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
• 높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
• 레벨 : 깊이와 같은 의미
• 서브트리 : 트리 내의 하위 집합으로, 트리 내에 있는 부분집합이라고도 한다.

이진 트리

자식의 노드 수가 두 개 이하인 트리

분류

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

이진 탐색 트리(BST)

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

• 왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져 있어서 검색에 용이하다.
• 요소를 찾을 때 시간 복잡도 : O(log n)
• 최악의 경우 : O(n) - 삽입 순서에 따라 선형적일 수 있기 때문이다.

AVL 트리(Adelson-Velsky and Landis tree)

최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리

• 두 자식 서브트리의 높이는 항상 최대 1만큼 차이가 난다.
• 선형적인 트리 형태를 가질 때 시간 복잡도 : 최악의 경우 O(n)
• 탐색, 삽입, 삭제 시간 복잡도 : O(log n)
  • 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다.
• 최악의 경우를 배제하고 항상 균형 잡힌 트리로 만들자.

레드 블랙 트리

균형 이진 탐색 트리

• 탐색, 삽입, 삭제 시간 복잡도 : O(log n)
• 각 노드는 빨간색 또는 검은색 색상을 나타내는 추가 비트를 저장한다.
• 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용된다.
• 모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.

3. 힙

---

완전 이진 트리 기반의 자료 구조로, 최소힙과 최대힙이 있다. 해당 힙에 따라 특정한 특징을 지킨 트리이다.

• 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
• 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
• 힙에는 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있다.

최대힙의 삽입

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

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

최대힙의 삭제

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

4. 우선순위 큐

---

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

• 힙을 기반으로 구현

5. 맵

---

특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조

• 레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬된다.

• map.put()

• get : key에 해당하는 value값을 얻는다.

  • getOrDefault : null 대신 디폴트 값을 얻고 싶은 경우에 사용

• size : Map 갯수 리턴

• remove : 맵의 항목 삭제하는 메서드

  • key값에 해당되는 아이템(key, value)을 삭제한 후 그 value 값을 리턴한다.

• keySet : 맵(Map)의 모든 Key를 모아서 리턴한다.

keySet() 메서드는 Map의 모든 Key를 모아서 Set 자료형으로 리턴한다. Set 자료형은 잠시후에 알아본다. Set 자료형은 다음과 같이 List 자료형으로 바꾸어 사용할수도 있다.

List<String> keyList =newArrayList<>(map.keySet());

6. 셋(set)

---

특정 순서에 따라 고유한 요소를 저장하는 컨테이너

중복되는 요소는 없고 오로지 희소한(unique) 값만 저장하는 자료 구조

7. 해시 테이블

---

무한에 가까운 데이터(키)들을 유한한 개수의 해시 값으로 매핑한 테이블

이를 통해 작은 크기의 캐시 메모리도로 프로세스를 관리하도록 할 수 있다.

• 삽입, 삭제, 탐색 시간 복잡도 : O(1)