시간이 너무 빠르다 빨라~
벌써 한주의 끝인 금요일이다.

image

자료구조를 공부 시작하고 자료구조에 대한 문제를 풀어보고 있었는데
어제 Queue문제를 풀다가 새벽2시에 자버렸다..

결국은 다풀고 잠을 청했다.
해결했다는 점에서 너무 뿌듯하긴 했지만
레퍼런스코드에 답이 나와 조금 다른걸 보니 어떻게 풀어야
좋은 방법일지 오늘 공부해보고 나머지 자료구조에 대한
공부를 시작하는 날이다.

오늘은 자료구조의
Graph, Tree, BST (Binary Serach Tree에 대해 공부해볼 예정이다.
이번 섹션 초반에는 알고리즘과 자료구조에 대한
공부가 주를 이룰 것 같다. 알고리즘 문제 풀이에 대한 사고력을
점점 길러간다는 점이 조금더 나를 강하게 만드는 것 같기도..?
공부를 시작해보자!


Tree

image

자료구조에서 트리구조는
나무의 뿌리모양을 생각하면된다. 가지가 뻗어나가는 모양의 자료 구조이고
무방향으로 연결된 계층적 자료구조이다.

이렇게 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 구조를
비선형 구조라고 한다.

루트(Root) : 하나의 꼭짓점 데이터를 시작으로 여러개의 데이터를 edge로 연결해준다.
노드(Node) : 각 데이터를 노드라고한다. 두개의 노드는 상하계측으로 부모/자식 관계를 가진다.
리프노드(Leaf Node) : 자식이 없는 도드를 리프노드라고 한다.
깊이(Depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다. (루트부터 0)
레벨(Level) : 같은 깊이를 가지고 있는 노드를 묶어서 레벨이라고 표현한다.
높이(Height) : 트리 구조에서 리프 노드를 기준으로 루트까지의 높이를 표현할 수 있다.
서브트리(Sub tree) : 트리 내부에서 트리 구조를 갖춘 작은 트리를 서브 트리라고 한다.

트리구조의 대표적인 예로는 폴더 경로를 볼 수 있다.
자바프로그램도 마찬가지다.
java라는 폴더안에서 패키지로 쭉 뻗어나가는 모습들이다.

image


Graph

image

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조다.
위의 예제는 인접 행렬의 예제이다.

두 정점을 이어주는 간선이 있다면 이 두정점을 인접하다고 이야기하고
정점이 이어져 있다면 1, 이어져 있지 않다면 0으로 표시하는 일종의 표로
나타내는 표기법이다.

2차원 배열을 만들어 그래프를 표시할 수 있다.
A는 B와 ,E와 연결되어있어 1로 표시하고
B는 A와 C와 E랑 연결되어있어 각각 연결된 자리에 1로 값을 표시했다.

여기서 알 수 있는 그래프의 구조는
1). 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
2). 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어져야한다.
3). 하나의 점을 그래프에서는 정점(Vertex)라고 표현하고, 선은 간선(Edge)라고한다

정점(vertax) : 노드 라고도 하며 데이터 저장되는 그래프 원소다.
간선(edge) : 정점 간의 관계를 나타낸다. (정점을 이어주는 선)
인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을뜻한다.
진입차수 (in-degree) : 한 정점에 진입하는 간선이 몇 개인지를 나타낸다.
진출차수 (out-degree) : 한 정점에 진출하는 간선이 몇 개인지를 나타낸다.


BST (Binary Search Tree)

image

한국어로 직역하면 이진탐색트리라고 부른다.
효율적인 탐색을 위해 만들어진 자료구조이다.
이진트리는 자식노드가 최대 두개인 노드들로 구성된 트리이다.
왼쪽 자식과 오른쪽 자식 노드로 나뉘며
자료를 삽입 삭제 방법에 따라 3가지로 나눠진다.

image

정 이진 트리                                           완전 이진 트리                                        포화 이진 트리

이진 트리 탐색에 가장 중요한 특징은
루트에서 뻗어나온 노드들은
자식기준으로 부모의 값보다 작으면 왼쪽, 크면 오른쪽에 저장하는 특징이있다.

순회 방법
전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문
중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문
층별 순회(level order traverse) : 위 쪽 node들 부터 아래방향으로 차례로 방문

오늘은 자료구조 tree, graph, BST에 대해 공부했다.
아직도 알고리즘이 조금 어색하고 어려워
이 자료구조들을 어떻게 적용해서 문제를 풀면 좋을지 아직
크게 와닿지는 않는다. 특히 그래프같은 경우가 조금
어느 상황이때 적용을해야 좋을지 아직 이해가 잘 되지 않는다 ㅠㅠ.

오늘 공부의 가장 주를 이룬 것은
이러한 자료구조가 있고 이런 자료구조가 어떻게 내부에서 동작하는지
직접 간단하게 프로그램을 만들어 테스트해보는게
오늘의 공부를 주를 이루었다.

매일매일 새로운게 나와 머리가 터질지경이지만
주말에 쉬면서 잘 정리해보아야겠다.

오늘 공부는 여기서 끝!


오늘의 커피량: ☕️ ☕️ ☕️ ☕️
오늘의 점심: 라면, 계란부침