09.26 스물 여섯 번째 수업 (tree, graph)

 

 

오늘은 tree와 graph에 대한 자료구조에 대해서 학습하였다.

 

---

Tree

 

단방향 그래프의 한 구조이다.

데이터가 바로 아래에 하나 이상의 데이터에 무방향으로 연결된 계층적 연결구조다.

나무의 뿌리에서 줄기가 퍼져나가는 모습의 반대 모습을 생각하면 된다.

루트, 노드, 부모 노드, 자식 노드, 리프 등으로 이루어져 있고 깊이와 레벨도 따질 수 있다.

 

트리 중 가장 많이 쓰이는 것은 이진 트리와 이진 탐색 트리이다.

이진트리는 자식 노드가 최대 2개인 노드들로 구성된 트리이다.

정 이진 트리 (노드가 0개 혹은 2개의 자식 노드 가짐),

완전 이진 트리 (마지막 레벨 제외 모든 노드가 차 있고 마지막 레벨 노드 또한 왼쪽은 차 있어야 함),

포화 이진 트리이진트리 ( 정 이진트리면서 완전 이진트리, 모든 리프 노드 레벨이 동일하고 모든 레벨이 가득 채워져 있음)

으로 나눌 수 있다.

이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.

 

이러한 트리들은 특정 목적을 위해 순회할 수 있다.

순회 방법에는

전위 순회 (root - left - right)

중위 순회 (left - root - right)

후위 순회 (left - right - root)

로 나눌 수 있다.

 

 

Graph

 

여러 개의 점들이 서로 복잡하게 연결되어 있는 자료구조이다.

데이터가 저장되는 기본 원소인 정점과 정점 간의 관계를 나타내는 간선으로 이루어져 있다.

추가적으로 인접 정점, 가중치/비가중치 그래프, 진입/진출 차수, 무향 그래프 등도 존재한다.

 

표현 방식에 따라 

서로 다른 정점들이 인접한 상태인지를 2차원 배열의 형태로 나타내는 인접 행렬과

정점들이 어떤 정점과 인접하는지를 리스트의 형태로 나타낸 인접 리스트로 나눌 수 있다.

 

그래프의 탐색은 하나의 정점에서 시작하여 모든 정점을 한 번씩 탐색해야 한다.

너비우선탐색(BFS, Breadth-First Search) = 한 정점을 기준으로 가까운 정점부터 탐색 (전체적으로 훑어보는 느낌)
깊이우선탐색(DFS, Depth-First Search) = 하나의 경로를 끝까지 탐색한 후 다시 기준 정점으로 돌아와서 반복

으로 나눌 수 있다.

그래프의 규모가 클수록 DFS를, 규모가 작고 깊이가 얕다면 BFS를 쓴다.

 

+

추가적으로 Deque (스택과 큐의 구조가 합쳐짐),

Linked List (연속된 공간에 메모리 저장하는 배열과 다르게 흩어져 있는 공간에 노드들의 연결로 이루어짐),

Hash Table (해시함수를 사용하여 변환한 해시를 인덱스로 삼아 키와 데이터를 저장),

Heap Tree (우선 순위에 따라 빠르게 자료를 검색할 수 있는 구조, 부모 노드의 값은 자식 노드 값보다 항상 크거나 작게

정렬하는 느슨한 정렬 구조를 가짐)을 학습하였다.

 

---

 

오늘의 일기

 

오늘도 페어 프로그래밍을 통해 문제를 페어 분과 같이 풀 수 있었다.

오늘의 문제는 더욱 극악무도 했다.

Tree구현, 인접 행렬 - 인접 리스트 구현, 이진 탐색 트리 구현까지는 IDE를 이용해 구조를 조금이나마 이해할 수 있었고

인접 행렬 생성하기 (주어진 2차원 배열을 입력받아 인접 행렬을 생성) 까지는 괜찮았다.

그 뒤에 나오는 인접 행렬 길 찾기 (갔던 행을 따로 저장해야 함), DFS/BFS의 개념을 생각해서 풀어야 하는 연결된 정점들,

추가적으로 건드려보지도 못했지만 엄청난 난이도를 자랑하는 바코드 문제까지..

문제를 풀면서 아.. 난 여기까지인가..라는 생각이 들 정도로 난이도가 어려웠다.

그래도 크루님께서 자료구조 알고리즘은 지금 당장 어려운 게 당연하고, 이해하지 못해도 괜찮다.

실시간 세션에서의 문제풀이가 이해가 된다면 문제를 다시 한번 풀어보면서 이해해보라고 다독여주셨기에 

넘어갈 수 있던 것 같다.

혼자 문제를 다시 풀어보면서 개념을 조금이나마 더 이해하려고 노력해봐야겠다.

더 어려워질 내일을 위해서라도 말이다.