이머시브 코스 TIL 2주차 모음

0302.화, 0303.수

sprint - BeesBeesBees, Subclass Dance Party 진행..

0304.목

Stack

• 자료를 쌓는 자료구조로, FILO(First In Last Out) 혹은 LIFO(Last In First Out)
• 실사용 예) 브라우저에서 뒤로가기, 앞으로가기 기능 구현

const stack = []
stack.push(1);stack.push(2);stack.push(3);stack.push(4);
console.log(stack) // [1, 2, 3, 4]
stack.pop();stack.pop();
console.log(stack) // [1, 2]

Queue

• 대기 행렬같은 개념으로, FIFO(First In First Out) 혹은 LILO(Last In Last Out)

const queue = []
queue.push(1);queue.push(2);queue.push(3);queue.push(4);
console.log(queue) // [1, 2, 3, 4]
queue.shift();queue.shift();
console.log(queue) // [3, 4]

Graph

• 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
• 정점(vertex)
• 간선(edge)
• 무방향그래프(undirected graph)
• 진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇개인지를 나타냄
• 인접(adjacency) : 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
• 자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 '자기 루프를 가졌다'라고 표현, 다른 정점을 거치지 않는다는 것이 특징
• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 '사이클이 있다'고 표현

Tree

• 일방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태를 띔
• 루트(root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결
  이 데이터들을 노드(node)라고 하며, 상위 노드와 하위 노드가 연결되면 부모/자식 관계를 가짐
  같은 레벨에 나란히 있는 노드들은 형제 노드(sibling node)
• 루트에서 자신에게 걸리는 거리를 레벨(level)
  루트부터 가장 안쪽에 있는 노드까지의 레벨을 트리의 높이(height)
  특정 노드부터 시작하여 루트까지의 레벨을 노드의 깊이(depth)

Binary Search Tree

• 자식 노드가 최대 두 개인 노드들로 구성된 트리를 이진 트리라고 정의
• 정 이진 트리(full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖음
• 완전 이진 트리(complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도되지만 왼쪽이 채워져야 함
• 포화 이진 트리(perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리

0305.금

Tree traversal

• 어떠한 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 함
  
• 전위(preorder) 순회 : 루트 노드부터 방문하여 왼쪽 서브트리를 둘러본 뒤, 오른쪽 탐색을 함
  A - B - D - H - I - E - J - K - C - F - L - M - G - N - O
• 중위(inorder) 순회 : 루트를 가운데에 두고 순회, 제일 왼쪽 끝에 있는 노드부터 루트, 오른쪽에 있는 노드로 이동
  H - D - I - B - J - E - K - A - L - F - M - C - N - G - O
• 후위(postorder) 순회 : 왼쪽 서브트리부터 오른쪽 서브트리를 모두 방문한 다음에 루트를 방문
  H - I - D - J - K - E - B - L - M - F - N - O - G - C - A

BFS / DFS

• BFS(Breadth First Search): 너비 우선 탐색으로, 가까운 정점부터 탐색
• DFS(Depth First Search) : 깊이 우선 탐색으로, 하나의 경로를 끝까지 탐색한 후, 다음 경로를 탐색