3주차 질문 목록

[blcklamb]

• 일시: 1월 29일 (월) 22시
• 범위:
  • Array
  • LinkedList
  • Array & ArrayList & LinkedList
  • 스택(Stack) & 큐(Queue)
  • 힙(Heap)
  • 트리(Tree)
  • 이진탐색트리(Binary Search Tree)
  • 해시(Hash)
  • 트라이(Trie)
  • B-Tree & B+Tree

각자 질문한 것을 comment로 달아주세요.

[freemjstudio]

Array와 LinkedList의 장점과 단점에 대해 시간 복잡도를 가지고 설명해주세요.

Array의 장점은 순차적으로 데이터를 저장할 수 있다는 것입니다. 데이터에 순서가 있으므로 index를 갖게 되며, index를 이용하여 자료의 탐색을 O(1)의 시간복잡도로 할 수 있습니다.

반면 데이터가 순차적으로 존재하기 때문에 새로운 데이터를 삽입하거나 삭제하는 경우 그 뒤의 모든 데이터들을 한칸씩 움직여주어야 한다는 단점이 있습니다. 이 경우 O(N) 의 시간 복잡도를 가집니다.

LinkedList의 경우 삽입과 삭제 연산에 O(1)의 시간복잡도를 가집니다. 반면, 탐색을 하는 경우 array 처럼 index를 이용하여 바로 접근할 수 없으며 선형 탐색을 해야 하므로 O(N)의 시간복잡도를 가집니다.

Binary Tree와 BST(이진탐색 트리)의 차이점에 대해 설명해주세요.

이진 트리는 자식 노드가 최대 2개인 노드들로 구성된 트리이다.

반면에, 이진 탐색 트리 이진탐색과 연결리스트를 합하여 장점을 얻는 자료구조이다. 이진탐색트리의 경우 각 노드의 왼쪽 서브트리의 노드들은 부모노드보다 작고, 오른쪽 서브트리의 노드들은 부모노드보다 크다. 또한 중복된 노드가 없어야 한다.

Binary Tree에서 leaf node 까지 탐색하기 위해서 어떻게 하나요 ?

1. DFS, 깊이 우선 탐색

루트 노드에서 시작하여 각 분기를 깊게 탐색하는 방법이다.

전위 순회, 중위 순회, 후위 순회가 있다.

전위 순회는 (Pre-order) 현재 노드를 방문하고 왼쪽 하위 트리를 방문한 후, 오른쪽 하위 트리를 방문한다.

중위 순회 (In-order) 는 왼쪽 하위트리를 방문(중위 순회 한)후, 현재 노드를 방문하고, 오른쪽 하위 트리를 방문한다.

후위 순회 (Post-order) 는 왼쪽 하위 트리를 순회하고, 오른쪽 하위트리를 순회한 후, 현재 노드를 방문한다.

2. BFS, 너비 우선 탐색

각 트리의 레벨을 순서대로 왼쪽에서 오른쪽으로 탐색하는 방법이다. 주로 queue를 사용하여 구현한다.

루트 노드를 queue에 삽입하고, queue가 비어있지 않는 동안 계속 다음 작업을 반복한다. a. queue에서 노드를 하나 꺼내서 처리한다. b. 해당 노드의 왼쪽 자식 노드가 있으면 queue에 삽입한다. c. 해당 노드의 오른쪽 자식 노드가 있으면 queue에 삽입한다.

[blcklamb]

stack 두 개를 이용하여 queue를 구현해 주세요.

enqueue를 구현하는 stack을 instack, dequeue를 구현하는 stack을 outstack이라고 가정하겠습니다. 첫 번째로 enqueue하는 것은 stack의 push와 동일하게 구현할 수 있습니다. dequeue를 구현하기 위해서 instack을 pop한 것을 순서대로 outstack에 push합니다. instack이 빌 때까지 해당 작업을 수행한 뒤 outstack을 pop하면 dequeue를 구현할 수 있습니다.

// javascript
class Queue {
  constructor() {
    this.instack = [];
    this.outstack = [];
  }
  enqueue(element) {
    this.instack.push(element);
  }
  dequeue() {
    if (this.outstack.length === 0) {
      if (this.instack.length === 0) {
        throw new Error("Cannot dequeue, already empty");
      }
      while (this.instack.length > 0) {
        this.outstack.push(this.instack.pop());
      }
    }
    return this.outstack.pop();
  }
}

# python
class Queue(object):
  def __init__(self):
    self.instack=[]
    self.outstack=[]

  def enqueue(self,element):
    self.instack.append(element)

  def dequeue(self):
    if not self.outstack:
        if not self.instack:
          raise Exception("Cannot dequeue, already empty")
        while self.instack:
          self.outstack.append(self.instack.pop())
    return self.outstack.pop()

queue 두 개를 이용하여 stack을 구현해 주세요.

queue1, queue2가 있다고 가정하겠습니다. push를 구현하기 위해 queue1에 enqueue합니다. pop을 구현하기 위해서는 queue1의 원소의 개수가 1이 될 때까지 queue1을 dequeue하여 queue2에 enqueue합니다. queue1에 하나 남은 원소를 dequeue하여 pop의 결과를 반환합니다. 마지막으로 queue1과 queue2를 swap하여 다음 pop을 대비하면 됩니다.

// javascript
class Stack(){
  constructor(){
    this.queue1 = []
    this.queue2 = []
  }
  push(element){
    this.queue1.push(element)
  }
  pop(){
    if (this.queue1.length === 0){
      throw new Error("Cannot pop, alreay empty")
    }
    while (this.queue1.length > 1){
      this.queue2.push(this.queue1.shift())
    }
    const poppedElement = this.queue1.shift()
    [this.queue1, this.queue2] = [this.queue1, []]
    return poppedElement
  }
}

# python
import queue

class Stack(object):
  def __init__(self):
    self.q1 = queue.Queue()
    self.q2 = queue.Queue()

  def push(self, element):
    self.q1.put(element)

  def pop(self):
    if self.q1.qsize() == 0:
      raise Exception("Cannot pop, alreay empty")
    while self.q1.qsize() > 1:
      self.q2.put(self.q1.get())

    popped_element = self.q1.get()
    self.q1, self.q2 = self.q2, queue.Queue()

    return popped_element

Dynamic Array를 Linked list와 비교하여 장단점을 설명해 주세요.

Linked List와 비교했을 때, Dynamic Array의 장점은 데이터 접근과 할당이 O(1)로 굉장히 빠릅니다. 이는 index 접근하는 방법이 산술적인 연산 [배열 첫 data의 주소값] + [offset]으로 이루어져 있기 때문입니다. 그리고 Dynamic Array의 맨 뒤에 데이터를 추가하거나 삭제하는 것이 상대적으로 빠릅니다.(O(1))
Linked List와 비교했을 때, Dynamic Array의 단점은 Dynamic Array의 맨 끝이 아닌 곳에 data를 insert or remove할 때, 느린 편입니다(O(n)). 느린 이유는 메모리상에서 연속적으로 데이터들이 저장되어 있기 때문에, 데이터를 추가 삭제할 때 뒤에 있는 data들을 모두 한칸씩 shift 해야되기 때문입니다. 그리고 Dynamic Array의 특성 상 resize를 해야할 때, 예상치 못하게 현저히 낮은 performance가 발생합니다. resize에 시간이 많이 걸리므로 필요한 것 이상 memory공간을 할당받습니다. 따라서 사용하지 않고 있는 낭비되는 메모리공간이 발생합니다.

해시 충돌(Hash Collision)이 발생하는 경우의 해결 방법에 대해 설명하고, 각 방법의 장단점을 언급해보세요.

Hash Collision이란 서로 다른 key의 해시값이 똑같은 경우를 말합니다. 즉, 중복되는 key는 없지만 해시값은 중복될 수 있는데 이 때 collision이 발생했다고 합니다.
따라서 collision이 최대한 적게 나도록 Hash Function을 잘 설계해야하고, 어쩔 수 없이 collision이 발생하는 경우 연결리스트로 노드를 계속 추가해나가는 seperate chaining 방법을 선택할 수 있습니다. 쉽고 간단하게 구현이 가능하지만 메모리 소비가 증가하는 단점을 가지고 있습니다. 또는 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용하는 open addressing등의 방법을 사용하여 해결합니다. 이는 추가적인 메모리 사용이 적지만 클러스터링과 선형 검색에 의한 성능 저하가 발생할 수 있습니다.

[Kim-Ju-won]

1. 떤 것이 좋은 해쉬 함수인가요? 3가지 조건을 이용해서 설명해주세요
2. 일반 Binary Tree, Binary Search Tree의 성능을 비교해주세요
3. 그래프와 트리의 공통점과 차이점을 설명해주세요.

[maintain0404]

1. 우선순위 큐 구현에 힙을 사용하는 이유를 설명해주세요.
   • 우선순위 큐는 우선순위가 높은 자료가 가장 먼저 나오는 큐 자료구조 변형입니다. 힙은 트리의 일종으로 항상 루트 노드에 최대(최대 큐 기준)값이 있어 우선순위가 높은 자료를 먼저 찾을 수 있고, 삽입/삭제가 O(log N)으로 빠릅니다.
2. B-Tree와 B+Tree의 차이점을 설명해주세요.
   • B 트리는 이진탐색트리를 개선해서 자식 노드가 2개 이상인 트리입니다. B-Tree는 중간 노드와 리프 노드 모두 key와 데이터를 가지고, B+Tree는 중간 노드는 key만 가지고 리프 노드는 key와 데이터를 가진다는 차이가 있습니다.

[blcklamb]

@maintain0404 제가 우선순위 큐/힙을 더 찾아보았는데요. 태인님께서 말씀해주신대로, 우선순위큐를 구현할 때 힙을 사용하는 것이 맞습니다. 구현할 때 list, linked list로도 구현할 수 있는데 operation의 시간복잡도가 push-O(logN), pop-O(logN)으로 가장 효율적이기 때문에 힙을 사용한다로 대답했었어야 했네요 🥲 그리고 제가 오해했던 부분은 'Heap은 그 자체로 우선순위큐(priority queue)의 구현과 일치합니다.'라는 문장이었어요. 이 부분에서 '힙 구현할 때 우선순위 큐를 쓰는구나'라고 잘못 이해했습니다. 원래라면 힙은 그 자체로 우선순위를 구현할 때 쓰는 자료구조라고 이해했었어야 했습니다. 다음부터는 조금 더 확실하게 공부하고 오겠습니다, 정확하게 집어주셔서 감사해요, 태인님!