오늘한일
원래 어제 Graph와 Tree에 대해서는 어제 학습이 되어야 했지만,
이해하는데 시간이 오래걸려 오늘 뒤늦게 학습하였다.
개념에 대해서는 이해를 할 수 있지만, 이를 활용한 알고리즘 풀이가 너무 힘들었다.
그리고 알고리즘을 하나도 못건드리는 내자신에 대해서 조언을 얻고싶어,
교육 엔지니어와 체크인을 진행하였다.
Achievement Goals
(이해한대로 작성하였기에 틀릴수도 있습니다. 계속 공부하며 수정해 나가겠습니다.)
-트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
-Tree, Graph 자료구조에 대해 이해할 수 있다.
Graph
보통 Graph라고 하면 x축 y축을 기준으로 상승 하락을 표현하는 자료를 생각할 것이다.
하지만 컴퓨터 공학에서 이야기하는 자료구조 Graph는 전혀 다른 모습을 가지고 있다.
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.
Graph는 노드(Node)와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조이다.
이미지에서 숫자들은 정점(vertex)이라고 표현하고, 선은 간선(edge) 이라고 표현한다.
즉 연결되어 있는 객체 간의 관계를 표현할 수 있다.
Graph를 실사용 하는 예는 지하철 노선도 같은 것으로 특정 위치(역)을 표시하는 정점이 있고, 정점과 정점을 연결하는 간선이 있다.
Graph에는 여러가지 특성이 있다.
무방향 그래프 VS 방향 그래프
- 무방향 그래프(Undirected Graph)
- 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
- 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
- (A, B)는 (B, A) 동일
- Ex) 양방향 통행 도로, 네비게이션
- 방향 그래프(Directed Graph)
- 간선에 방향성이 존재하는 그래프
- A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
- <A, B>는 <B, A>는 다름
- Ex) 일방 통행 도로
인접 행렬
두 정점을 바로 이어 주는 간선이 있다면 두 정점은 인접하다고 이야기한다.
인접 행렬은 정점들간의 인접함을 표시해 주는 행렬으로 2차원 배열의 모습을 가지고 있다.
만약 A라는 정점과 B라는 정점이 이어져 있다면 1, 이어져 있지 않다면 0으로 표시하는 일종의 표와 같은 모습이다.
세로축(열)은 전역 배열의 배열인 요소들
가로축(행)은 배열인 요소의 요소들
만약 정점0에서 정점2가 이어져있다면, 전역배열의 0번째 배열에 2를 가리키는 3번째 요소가 1로 변경될것이다. //Directed
정점0과 정점2가 서로 이어져있다면, 위와 동시에 전역배열의 3번째 배열에 0번째 요소가 1로 변경될것이다. //Undirected
인접행렬은 가장 빠른 경로를 찾고자 할 때 주로 사용된다.
Tree
Tree는 무방향 그래프의 한 구조로 나무와 닮아 있다고 해서 Tree 구조라는 이름이 붙여졌다.
나뭇가지에서 여러 가지가 나오는 것과 같은 구조형태이다. 그안에 담긴 데이터는 Node라고 하면 여러 가지가 나오는 것은 부모Node가 자식Node를 가지고 있다는 것이다. 컴퓨터 폴더정리, html구조를 생각하면 된다.
하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조로 되어 있고, 계층적으로 표현이 되며 루트(Root)라는 최상단 데이터에서 아래로만 뻗기 때문에 사이클이 없다.
Tree traversal
트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.
이를 순회하는 방법은 여러가지가 있다.
-
전위순회
- 제일 처음 방문할 노드는 루트입니다. 루트를 기준으로 왼쪽의 노드들을 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 탐색
-
중위순회
- 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색
-
후위순회
- 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막으로 루트를 방문
현재 상태
- Graph는 실제로도 어려운 개념이라 이해를 많이 못하고있다.
- 문제를 해결할때 콘솔로그 디버그를 자주 사용하는데 이게 아주 좋은 습관이라고한다.
- 좌절감을 느낄때마다 마인드 컨트롤을 할 방법을 찾아야겠다.
참고 사이트
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
