내일배움캠프 D+110: 0804

📚 알고보면 알기쉬운 알고리즘

✳ 4주차 ❇

✔ Tree

▶ 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조

• 이진 트리(Binary Tree)
  각 노드가 최대 두 개의 자식을 가진다
• 완전 이진 트리(Complete Binary Tree) - 최대 높이 $O(logN)$
  노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입한다.
  아래와 같이 배열로 만들 수 있다.
  1. 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
  2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스
  3. 현재 인덱스 // 2 -> 부모의 인덱스

✔ Heap

▶ 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨, 혹은 그 반대인 자료 구조

✔ Graph

▶ 연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조

노드(Node): 연결 관계를 가진 각 데이터를 의미. 정점(Vertex)이라고도 함.
간선(Edge): 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

✔ DFS & BFS

• DFS
  ▶ 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.

• BFS
  ▶ 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다.

✔ Dynamic Programming

▶ 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
재귀함수와 비슷하나 그 결과를 기록하고 이용한다.

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,
비선형구조는 표현에 초점이 맞춰져 있다!