24일차: 자료구조(Graph, Tree, BST)

❯ Graph

여러 점들이 서로 복잡하게 연결된 관계를 나타내는 자료구조.

흔히 그래프라고 생각하면 수학에서 접했던 이차함수그래프, 정규분포그래프 등을 생각하기 쉽다.

하지만 컴퓨터 공학에서 이야기하는 자료구조로서의 Graph는 여러개의 점이 선으로 이어진 네트워크망 구조를 가진다.

정점과 간선으로 표현된 간단한 그래프 자료구조

• 그래프의 구조
  점간의 직접적인 관계가 있으면 두 점 사이를 이어주는 선이 있다. 간접적인 관계라면 몇개의 점과 선을 통해 이어진다.
  이 때 하나의 점을 정점(Vertex), 이를 잇는 선은 간선(edge)이라고 한다.
• 그래프의 표현방식
  두 정점을 잇는 간선이 있다면 이 두 정점은 인접한 것이다. 이를 표현하는 방법으로는 인접행렬을 이용하는 방법과 인접리스트를 사용하는 방법이 있다.
  1) 인접행렬 : 두 정점간의 관계가 있는지 없는지를 확인할 때 사용할 수 있다.
        예를 들어 인접 행렬에서 이어져있으면 1, 없으면 0으로 표현할 수 있다. ex) [0][2] = 1 // A 에서 C로 진출하는 간선이 있다. 
        연결의 강도를 포함하는지 유무에 따라 가중치 / 비가중치 그래프로 구분된다.
  2) 인접리스트: 한 정점에서 시작되어 어떤 정점과 인접하는지를 리스트 형태로 표현할 수 있다. 각 정점마다 하나의 리스트를 갖는다.
        위 그림을 표현하면 B -> A -> C -> null 과 같다.

❯ Tree

단방향 그래프의 일종으로, 나무를 뒤집어놓은 형태를 가진다. Root Node에서 아래로 뻗는 계층적 데이터 구조를 가진다.

root인 A에서부터 시작하는 트리

가장 상단의 노드를 루트(Root)라고 하며, 상하관계로 연결된 노드를 부모/자식 관계라고 한다. 자식이 없는 노드는 리프노드(Leaf Node)라고 한다.

트리구조에서 사용하는 용어는 아래와 같은 것들이 있다.

• 깊이(Depth) : 루트로부터 하위 계층 특정 높이까지의 깊이. 위의 경우 B의 깊이는 1이 된다.
• 레벨(Level) : 같은 깊이를 가진 노드들은 동일한 레벨에 있게되며 형제노드(Sibling Node)라고 한다.
        위의 경우 A 의 레벨은 1, B, C의 레벨은 2가 되며 B와 C는 형제노드이다.
• 높이(Height) : 리프 노드를 기준으로 루트까지의 높이를 나타낸다. 각 자식노드로부터 구한 높이의 최대값을 높이로 가진다.
        위의 경우 높이는 2이다.
• 서브트리(Sub tree) : 트리구조 안에 있는 작은 트리구조를 의미한다. 위의 경우 B,D,E 를 서브트리라고 할 수 있다.
• 차수(Degree) : 각 노드에서 자식방향으로의 간선 개수를 의미한다. B의 차수는 2이며 C의 차수는 1이다.

❯ BST(Binaray Search Tree)

트리구조는 데이터 탐색을 위해 사용할 수 있다. 이 때 효율적으로 사용가능한 것이 이진 탐색 트리이다.

이진 트리란, 하나의 부모노드에서 최대 두개의 자식노드를 가지는 구조를 의미한다.

이진 탐색 트리란, 모든 왼쪽 자식노드의 값이 루트나 부모노드보다 작고, 오른쪽 자식노드의 값이 루트나 부모노드보다 큰 것을 의미한다.

이진트리의 종류와 특징

• 정 이진 트리(Full binary tree): 각 노드가 0개 혹은 2개의 자식 노드를 가짐
• 포화 이진 트리(Perfect binary tree): 정 이진 트리이면서 완전 이진 트리(모든 리프 노드의 레벨이 같고, 모든 레벨이 다 채워짐)
• 완전 이진 트리(Complete binary tree): 마지막레벨을 제외한 모든 노드가 가득 차있으며, 마지막 레벨의 노드의 왼쪽은 채워져있음

이진 탐색 트리

• 이진 탐색 속성이 이진 트리에 적용된 형태의 이진 트리를 말한다.
• 이진 탐색: 특정한 값을 찾기 위한 알고리즘으로, 오름차순으로 정렬된 데이터를 같은 두 부분으로 나눈 후 탐색이 필요한 부분에서만 탐색하도록 범위를 제한하여 값을 찾는 알고리즘이다. 트리 안에 찾고자 하는 값이 있을경우 트리 높이 이하의 탐색이 이루어지며, 값이 없을경우 트리 높이만큼 탐색이 진행된다.

---

이번주는 데이터 구조들에 대한 학습을 주로 했다. 아무래도 코드를 작성하면서 해야하는 내용이 많았다.

약간 수학문제 푸는 기분도 들고 꽤 재밌게 할 수 있었다. 마치 예전 수험생으로 돌아간 기분이었다.ㅎㅎ

물론 쉽게 풀리지 않는것들도 있어서 많은 시간을 할애해야했는데, 안풀리던 문제를 해결했을때의 성취감이 크게 느껴졌다.

다음주까지도 이런 수업 진행방식이 계속되는것으로 알고있는데 최대한 많은 케이스를 접해보고,

배운 내용 뿐만 아니라 구글링도 하면서 새로운 방법들도 많이 익혀보려고 노력해야겠다.