🎯 Achievement Goals

• 트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
  • Binary Search Tree를 이해할 수 있다.

👉 Graph

그래프는 내가 중고등학교때 배웠던 모습이랑은 완전 다른 형태였다. 프로그래밍 세계에서는 위와 같은 형태를 그래프라고 부른다.

오늘 배운 그래프와 트리는 비슷하게 생겼지만 개념은 완전 다르다. 트리도 노드와 엣지를 가지고 있어서 그래프의 한 종류에 속하지만 그래프에서는 계층(Level)이나 깊이(Depth)를 따지지 않기 때문에 트리랑 그래프는 다르다고 볼 수 있다.

그래프에서는 엣지의 방향이 있을 수도 있고 없을 수도 있다.

정점(Vertex)은 그래프에서 점을 표현하고, 간선(edge)은 그래프의 선을 표현한다.

인접행렬

인접(Adjacency)은 두 정점을 이어 주는 간선이 있다면 두 정점은 인접하다라고 표현한다.

만약 A라는 정점과 B라는 정점이 이어져 있다면 1, 이어져 있지 않다면 0으로 나타낸다.

A의 진출차수는 1개: A —> C
[0][2] === 1

B의 진출차수는 2개: B —> A, B —> C
[1][0] === 1
[1][2] === 1

C의 진출차수는 1개: C —> A
[2][0] === 1

인접행렬은 가장 빠른 경로를 찾고자 할 때 주로 사용하니 기억해두자!

👉 Tree

트리는 일방향 그래프의 한 구조로, 하나의 뿌리로 부터 가지가 사방으로 뻗은 형태를 띄우고 있기 때문에 트리라고 부른다. 실제 그래프 형태는 거꾸로 된 트리라고 생각하면 된다.

데이터를 순차적으로 나열시킨 선형 구조이 아닌 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조로 되어 있다.

트리는 데이터 바로 아래에 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조라고 할 수 있다.

👉 Binary Search Tree

트리는 효율적인 탐색을 위해 다양한 자료구조를 사용하는데, 오늘은 이진 탐색 트리에 대해 공부를 했다.

자식 노드가 최대 두개로 이루어진 트리를 이진 트리라고 부른다.

이진 트리 자료의 삽입, 삭제 방법에 따라 3가지로 분류 시킬 수 있다.

모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 특징을 가지고 있는 이진 트리를 이진 탐색 트리라고 정의한다.

🙌 느낀점

오늘 배운 자료구조에 대해서 구현하고 알고리즘을 푸는 시간을 가졌다.

어제 스택, 큐를 배웠을 때는 그나마 할만 했는데 오늘 배운 이진 탐색 트리는 진짜…. 개념은 이해를 하지만 그 개념을 가지고 구현을 하거나 알고리즘을 푸는 건 많이 버겁게 느껴진다 ㅜㅜ

내일 주말이니까 주말 동안 이진 탐색, 이진 탐색 트리 부분은 확실하게 짚고 넘어가자!

👊 내일의 TIW(today I Will)

스프린트 복습(스택, 큐, 이분탐색)