Tree
그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮았다고 해서 트리 구조라고 부른다.
- 하나의 데이터 아래에 여러 데이터가 존재할 수 있는 비선형 구조
- 시작 노드 -> 시작 노드 사이클 가능
이진트리
자식 노드가 최대 두 개인 노드로 구성된 트리입니다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.
- 정 이진트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖습니다.
- 포화 이진트리(Perfect binary tree) : 정 이진트리이면서 완전 이진트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
- 완전 이진트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
이진 탐색
정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘
- 배열의 중간에 내가 찾고자 하는 값이 있는지 확인한다.
- 중간값이 내가 찾고자 하는 값이 아닐 경우, 오름차순으로 정렬된 배열에서 중간값보다 큰 값인지 작은 값인지 판단한다.
- 찾고자 하는 값이 중간값보다 작은 값일 경우, 배열의 맨 앞부터 중간값 전까지의 범위를 탐색 범위로 잡고 탐색을 반복 수행한다.
- 찾고자 하는 값이 중간값보다 큰 값일 경우, 배열의 중간값의 다음 값부터 맨 마지막까지를 탐색 범위로 잡고 탐색을 반복 수행한다.
탐색 과정
- 루트 노드의 키와 찾고자 하는 값을 비교합니다. 만약 찾고자 하는 값이라면 탐색을 종료합니다.
- 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행합니다.
- 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행합니다.
Graph
여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조
- 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다.
- 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다.
- 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 합니다.
최단 경로 탐색
BFS(Breadth-First Search)
- 너비 우선 탐색
현재 있는 노드에서 가까운 곳부터 탐색하므로 경로를 탐색하는 도중 가장 먼저 발견한 해답이 최단거리라는 보장이 되기 때문에 사용
DFS(Depth-First Search)
- 깊이 우선 탐색
하나의 경로를 끝까지 탐색한 후, 아니면 다음 경로로 넘어가 탐색
BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.
열심히 기록할 예정🙃