📚 하루에 한번씩 배운 것과 지식을 정리하려고 쓰는 글

자료구조와 알고리즘

1. Stack, Queue에 대해서 설명해주세요.

---

• 답

  Stack은 먼저 들어온 자료가 나중에 나가는 것입니다. 즉 FILO(First In Last Out)입니다. Stack은 접근성에 제한이 있는 자료구조입니다. 오직 맨 위에 추가(push)할 수 있고, 맨 위에 것만 나갈(pop) 수 있습니다.

  Queue는 먼저 온 사람이 먼저 나가는 것입니다. 즉 FIFO(First In First Out)입니다. Enqueue(들어옴)과 Dequeue(나감) 두가지 동작만 허용된 자료구조입니다

  Stack과 Queue의 가장 큰 차이점은 item을 삭제할 때입니다. 스택은 가장 마지막에 추가되어 있던 item을 삭제하고, Queue는 처음으로 들어와 있던 item을 삭제합니다.

2. Heap, Priority Queue에 대해서 설명해주세요.

---

• 답

  힙은 특정 연산을 빠르게 수행하기 위한 이진 트리 자료 구조로 부모 노드와 자식 노드간의 일련의 규칙을 통해 일관성 있는 결과를 도출해내기 위한 자료구조이다.

  최소 힙은 부모가 자식보다 작은 이진 트리를 구성하며 루트노드가 즉 전체 데이터의 최솟값이 된다. 반대로 최대 힙은 부모가 자식보다 큰 자료구조이기 때문에 루트노드는 전체 데이터의 최댓값을 나타낸다.

  Binary Heap을 구현할 경우 이진 트리의 Root 노드부터 단일 leaf 노드까지의 순회 비용만 가질 뿐이므로 Insert와 Delete 연산이 모두 O(logN)의 복잡도를 가지며 최소힙/최대힙 과 같은 기능적 힙을 구현하는 경우, 조회(Peek)의 시간 복잡도는 O(1)로 아주 효율적이다.

  Priority Queue 를 Heap 을 이용해 만들 수 있지만 Heap 과 Priority Queue 간에는 직접적인 연관은 없으며 다만 구현에 있어서도, 기능에 있어서도 Heap 을 이용해 만드는 것이 효과적이므로 거의 동일어나 다름없이 혼용되고 있을 뿐이다.

  출처:

  https://jins-dev.tistory.com/entry/힙Heap-우선순위큐Priority-Queue-의-구현과-성질

  [Jins' Dev Inside]

3. Tree, Binary Tree, BST, AVL Tree에 대해서 설명해주세요.

---

• 답

  tree자료구조는 그래프의 한 종류로, 어떤 노드들의 집합으로 노드들은 각 서로 재사용 되지 않는 구조입니다. 또한 트리의 가장 빈번한 사용이 되는 Binary Tree에서 특정 노드에 대한 접근 O(N)이 아닌 O(logN)이 됨을 이용하는 것입니다.

  트리의 종류는 크게 Binary Tree와 None-Binary Tree로 나눌 수 있습니다. Binary Tree는 이진 트리로 각 노드에 대해서 두개 이하의 자식을 가짐을 의미하고, non-binary tree의 경우 노드의 자식 개수에 대한 제한이 없음을 의미합니다.

  이진트리는 활용도에 따라 여러 알고리즘으로 나뉘어집니다. BST(Binary-Search-Tree)는 가장 유명하고 접근성이 용이한 알고리즘입니다. 각 노드는 left Subtree 와 right Subtree의 루트를 자식으로 가지며 이때 왼쪽 서브트리는 자신보다 작은값을 오른쪽 서브트리는 자신보다 큰 값을 가지는 형태의 이진트리입니다. BST의 장점은 자료 입력,삭제,탐색 모두 시간복잡도가 O( log N ) 이라는 점입니다. 기본적인 배열 이진탐색의 경우 시간복잡도는 동일하지만 자료의 변경, 삭제가 불가능했습니다.

  AVL 트리는 이진탐색트리의 한 종류입니다. 이진 탐색 트리는 이진트리의 한 종류입니다. 따라서 AVL 트리는 이진트리와 이진탐색 트리의 특징들을 모두 갖고 있습니다.

  • AVL 트리의 특징

    1) 어떤 노드라도 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크지 않다. (최대 높이 차이는 1이다)

    ⇒ Binary Tree이면서 최대 높이 차이가 1이라는 말은 height = O(logN)이라는 것과 같다.

    2) 만약 특정 노드를 추가하거나 삭제했을 때 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 커지는 노드가 생긴다면, re-balancing을 통해 a 규칙에 어긋나지 않도록 한다.

    ⇒ 이 말은 AVL 트리는 자가 균형 이진 탐색 트리라는 말과 같다.

    3) 균형 트리이다. (높이 균형 트리)

    ⇒ 균형 트리는 아래 세가지 조건을 모두 만족하는 트리이다.

  1. 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이다.

  2. 왼쪽 서브트리가 균형 트리이다.

  3. 오른쪽 서브트리가 균형 트리이다.

     4) 각 노드는 균형값을 가지고 있으며 이 균형값은 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값이다. 이 값은 항상 {-1, 0, 1} 셋 중 하나의 값이어야 한다.

     5) 균형 값이 마이너스면 left-heavy, 플러스 값이면 right-heavy라고 한다.

     6) pivot 노드는 새로운 노드가 추가되었을 때 균형값에 변동이 발생하여 unbalanced 된 노드들 중 신규노드와 가장 가까운 노드를 말한다.

     AVL트리에 노드를 추가 또는 삭제를 하게 되면 스스로 균형을 맞추기 위해 트리의 회전을 할 필요가 있습니다.

  • 왼왼 : 부모 노드와 pivot 노드의 균형값이 모두 left-heavy인 경우

    ⇒ Single Right rotation (오른쪽으로 1회전)

  • 오오 : 부모 노드와 pivot 노드의 균형값이 모두 right-heavy인 경우

    ⇒ Single Left rotation (왼쪽으로 1회전)

  • 왼오 : 부모 노드와 pivot 노드의 균형값이 각각 right-heavy, left-heavy인 경우

    ⇒ Double Left-Right rotation (왼쪽으로 한번, 오른쪽으로 한번 총 두번의 회전)

  • 오왼 : 부모 노드와 pivot 노드의 균형값이 각각 left-heavy, right-heavy인 경우

    ⇒ Double Right-Left rotation (오른쪽으로 한번, 왼쪽으로 한번 총 두번의 회전)

    출처 :

    http://www.secmem.org/blog/2019/05/09/트리의-종류와-이해/

    https://keichee.tistory.com/441

4. DFS, BFS에 대해서 설명해주세요.

---

• 답

  DFS(깊이우선탐색)는 스택 혹은 재귀호출을 통해 그래프를 순회하는 방법입니다. 깊이우선탐색은 우선 나(현재 노드)를 먼저 방문하고 나와 연결된 다른 것들 중 하나를 방문하는 것입니다. 이때 방문했던 노드는 방문하지 않습니다.

  예를 들어, DFS 알고리즘은 미로를 탐색할 때 한 방향으로 모든 노드를 방문하다가 더 이상 다른 노드를 방문할 수 없는 노드에 이르렀을 때, 다시 가장 가까운 갈래길로 돌아가 방문하지 않은 노드 방향으로 다시 탐색을 같은 방법으로 이어나가는 방법과 유사하게 동작합니다. 특히 그래프에서 간선이나 변수 정보를 수시로 변경해야 하는 문제는 DFS를 활용하는 것이 효과적이라는 특징이 있습니다.

  BFS(너비우선탐색)은 Queue를 이용하여 그래프를 순회하는 방법입니다. 인접한 모든 노드들을 동시에 방문하여 탐색을 진행한다고 생각하면 됩니다.

  BFS 알고리즘은 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있는 알고리즘입니다. 그리고 "미로를 빠져나가는 최단 거리(경로)"를 구하는 문제 등에서 효과적으로 활용할 수 있는 알고리즘입니다

  출처:

  https://heytech.tistory.com/56

  [Hey Tech]