어제에 이어 자료구조의 종류에 대해 알아 볼 예정이다~
Stack과 Queue 연습문제를 푸는데 자꾸자꾸만 timeOut이 나거나 기분 나쁘게 에러가 나서 결국 레퍼런스를 보면 풀었다.
아니 왜 이론은 저렇게 쉬운데 구현하는건 막히는 것이야 ~ 😭😭
오늘은 이론보다는 연습문제를 푸는데 시간을 더 할애해야겠다고 생각했지만!
트리랑 그래프가 1시간밖에 안 주어져서 빨리 보는데도, 오버타임 됐다. ( 절레절레 )
이론만 보는게 아니라, 어제를 바탕으로 이걸 어떻게 구현할 것인가를 중점을 두었다.
키워드는 Tree, Graph 이다.
< Tree >
1. 개념
: 역나무 구조로, 데이터에 경로와 방향이 하나로 연결된 계층적 자료구조임. ( 비선형 구조 )
: 시작노드에서 다른 노드를 거쳐 시작노드로 돌아올 수 없음 .. 사이클이 없음.
( ex . 컴퓨터의 디렉토리 구조 )
2. 구조와 특징
각 데이터를 노드 ( Node ) , 트리 구조의 시작 노드를 루트 ( Root ) 라고 함.
노드들은 간선 ( Edge ) 로 연결되고, 각 상하 계층으로 부모, 자식 관계를 가짐.
자식노드가 없는 노드를 리프 노드 ( Leaf Node ) 라고 함.
-> 깊이 ( depth )
: 루트로부터 특정 하위 계층 노드까지의 깊이.
-> 레벨 ( Level )
: 같은 깊이를 가지는 노드를 묶어서 레벨로 표현할 수 있음. ( 같은 레벨에 있는 노드들을 형제노드 라고 함 )
-> 높이 ( Height )
: 리프노드를 기준으로, 루트까지의 높이.
3. 종류
-> 이진트리 ( Binary Tree )
: 자식 노드가 최대 2 개인 노드로 구성된 트리.
: 데이터가 정렬되어 있진 않다.
( 효율적인 검색과 정렬을 위해 사용됨 )
: 자료의 삽입, 삭제 방법에 따라 정 이진트리, 완전 이진트리, 포화 이진트리로 나뉨.
- 정 이진 트리 ( Full binary tree ) : 각 노드가 0개 혹은 2개의 자식 노드를 가짐.
- 포화 이진트리 ( Perfect binary tree ) : 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워진 트리.
- 완전 이진트리 ( Complete binary tree ) : 모든 노드가 가득 차고, 마지막 레벨만은 오른쪽이 비워도 되는 트리.
-> 이진 탐색 트리 ( Binary Search Tree )
: 이진트리에서 데이터가 정렬되어 있는 트리.
: 원하는 값을 탐색할 때 , 탐색 범위를 제한하여 원하는 값을 빨리 찾을 수 있도록 돕는 자료구조.
: 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐.
4. 트리 순회 방법
: 특정 목적으로 트리의 모든 노드를 한번 씩 방문하는 것을 트리 순회라고 함.
-> 전위 순회 ( Preoder Traverse )
: 루트를 기준으로 무조건 왼쪽 노드들을 순차적으로 둘러보는 방식.
노드가 리프노드라면, 다시 올라가 오른쪽을 탐색 함.
( 트리를 복사할 때 주로 사용 . )
-> 중위 순회 ( Inorder Traverse )
: 루트를 가운데에 둔 후 , 맨 왼쪽 노드부터 순회 함.
왼쪽 노드 순회가 끝나면, 루트를 걸쳐, 오른쪽 노드를 마저 탐색함.
( 오름차순을 가져올 때 주로 사용 )
-> 후위 순회 ( Postorder Traverse )
: 루트를 제일 마지막에 순회 함.
제일 왼쪽 끝 노드부터 순회하고, 오른쪽으로 이동한 후, 맨 마지막에 루트를 방문함.
( 트리를 삭제할 때 주로 사용 )
-> 레벨 순회 ( Levelorder Traverse )
: 트리의 레벨을 기준으로 동일한 레벨에서 왼쪽에서 오른쪽 순서로 순회.
< Graph >
1. 개념
: 여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조.
: 점 (노드 )을 정점 ( vertex ) , 관계를 나타내는 하나의 선을 간선 ( edge ) 라고 함.
두 정점을 바로 이어주는 간선이 있다면, 두 정점은 인접 정점이라고 함. ( 직접적인 관계 )
간선은 방향을 가질 수도 있음.
정점에 들어오는 간선과, 나가는 간선의 개수를 진입차수/ 진출차수라는 용어로 표현할 수 있음.
연결의 강도가 적혀져 있으면 가중치 그래프, 아니면 비가중치 그래프라고 함.
한 정점에서 출발해서 다시 해당 정점으로 올 수 있다면 사이클이 있다고 표현함.
2. 그래프 순회
BFS(Breadth-First Search)
: 가까운 정점을 기준으로 탐색.
( 최단 경로를 찾을 때 주로 사용 . )
DFS(Depth-First Search)
: 왼쪽 정점부터 리프 정점이 나올때까지 끝까지 순차적으로 탐색
( 모든 노드를 완전히 탐색할 수 있다는 장점이 있음. )