2020.06.15(월), 16(화) Sprint 2. Data Structure

Today I Learned(월)

Graph

• 간선의 방향 유무에 따라 무방향 그래프와 방향 그래프로 나뉜다.
• 무방향 그래프에서 최대 간선 수는 n(n-1)/2이다. (n은 정점의 수)
• 노드 간의 연결을 표현하는 방식으로는 인접 행렬 방식과 인접 리스트 방식이 있다.
• property: nodes
• method: addNode(node), contains(node), removeNode(node), hasEdge(fromNode, toNode), addEdge(fromNode, toNode), removeEdge(fromNode, toNode)

Tree

• 그래프의 한 종류로 다른 그래프와 차별되는 고유의 특성이 있다.
• root 노드가 존재하며 자식 노드가 있어 그 구조는 계층을 이룬다.
• property: value, children
• method: insertNode(value), contains(value)

BinarySearchTree

• 자식 노드는 2개만 지닐 수 있다.
• 부모 노드와 비교해 작으면 왼쪽 자식 노드, 크면 오른쪽 자식 노드로 배치된다.
• 배치가 잘 되었다면, 탐색의 시간 복잡도는 O(logN)을 가져 매우 빠르다.
• property: value, left, right
• method: insert(value), contains(value), inorder(callback)

Today I Learned(화)

시간 복잡도

• 문제를 해결하는데 소요되는 시간
• O(1) => O(logN) => O(N) => O(NlogN) => O(N^2) => O(c^N) => O(n!)

---

Questions

Graph

• 진입 차수, 진출 차수는 무엇인가?
  • 진입 차수(in-degree): 정점으로 향하는 간선의 수
  • 진출 차수(out-degree): 정점에서 나가는 간선의 수
• 그래프 구현 방식 중 인접 행렬 방식과 인접 리스트 방식의 차이는 무엇인가.
  • 인접 행렬 방식은 2중 배열을 이용하여 연결된 곳을 1, 끊긴 곳을 0으로 표현하는 방식이다.
    • adj[fromNode][toNode]: fromNode에서 toNode를 향하는 간선이 있으면 1, 없으면 0
    • 가중치가 있다면 1 대신 가중치의 값을 넣어준다.
  • 인접 리스트 방식은 노드와 연결된 다른 노드를 연결 리스트로 추가하는 방식이다.
    • adj.getNodeAt(i): i번째 노드에 연결된 노드를 갖는 연결 리스트

Tree

• depth와 height의 차이는 무엇인가? 참고

  • depth는 root 노드와 노드 중간에 있는 간선의 수이다. 그러므로, root 노드는 depth가 0이다.
  • height는 leaf 노드와 노드 중간에 있는 간선의 수이다. 그러므로, leaf 노드의 height는 0이다.

• Tree와 Graph의 차이는 무엇인가?

  • 트리는 그래프의 한 종류다. 그래프 중에서도 간선의 방향이 없고, Cycle이 없는 그래프를 트리라고 한다. 또한, 한 개의 root 노드를 지녀야 하며 모든 자식 노드는 하나의 부모 노드를 가진다. 간선은 항상 node 수 - 1이다.

Binary Search Tree

• 깊이 우선 탐색(DFS, Depth-First Search)은 무엇인가?

  • root 노드부터 시작하여 하나의 가지에서 마지막 depth를 발견할 때까지 전부 탐색하고 다음 가지로 넘어가 탐색을 계속하는 방식이다.
  • 너비 우선 탐색(BFS, Breadth-First Search) 방식도 있는데, DFS와는 정반대로 같은 depth를 가지는 노드를 모두 탐색한 뒤에 다음 depth로 넘어가는 방식이다.

• 이진 탐색 트리가 주어졌을 때, 다음과 같은 방법으로 탐색할 수 있는가?

  • 전위 순회(Preorder Traversal): 부모 -> 좌 -> 우

preorder(callback) {
  callback(this.value);
  if (this.left) {
    this.left.preorder(callback);
  }
  if (this.right) {
    this.right.preorder(callback);
  }
}

• 중위 순회(Inorder Traversal): 좌 -> 부모 -> 우

inorder(callback) {
  if (this.left) {
    this.left.inorder(callback);
  }
  callback(this.value);
  if (this.right) {
    this.right.inorder(callback);
  }
}

• 후위 순회(Postorder Traversal): 좌 -> 우 -> 부모

postorder(callback) {
  if (this.left) {
    this.left.postorder(callback);
  }
  if (this.right) {
    this.right.postorder(callback);
  }
  callback(this.value);
}

• 다음 이진 트리는 각각 어떤 특징을 가지고 있는가?
  • 정 이진 트리(Full Binary Tree)
    • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리. 자식 노드를 1개만 가진 노드가 없다.
  • 완전 이진 트리(Complete Binary Tree)
    • 마지막 레벨을 제외하고 모든 레벨에 노드가 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽으로 몰려 있어야 한다.
  • 포화 이진 트리(Perfected Binary Tree)
    • 모든 inner 노드가 두 개의 자식 노드를 가지며, 모든 leaf 노드가 동일한 깊이와 레벨을 가진다.