이머시브 과정 2주차 4째날이다.
오늘은 어제 배웠던 자료구조에 대해서 마저 배우고 코플릿 문제푸는 시간을 가졌다.
블로깅을 하며 배운것을 다시 한번 정리해보자 !
🔥Today Lesson🔥
- Graph
- Tree
- Binary Search Tree
- BFS / DFS
Graph 🚩
Graph란?
우리가 흔히 알고있는 그래프와 컴퓨터 세계에서의 그래프는 다르다.
자료구조에서 우리가 앞으로 알아가야할 그래프는 현실세계에서의 사물이나 추상적인 개념간의 연결관계를 선으로 나타낸것을 의미하며 여기서 말하는 사물이나 추상적인 개념을 정점(vertex) , 연결하는 선을 간선(edge) 이라고 한다.
알아둬야 할 그래프 용어들
-
무향그래프: A지역 B지역이 있다고 가정했을때 A와B가 서로 연결되어 있어서 쌍방 통행이 가능한 그래프를 말한다. 만약 일방통행 도로로 이루어져 있어서 A에서 B로 가는것이 불가능하면(혹은 그반대) 단방향그래프로 구현한다.
-
차수: 정점에 속해있는 간선의 수를 의미한다. 이때 한 정점에 진입하는 간선을(진입차수) 나가는 간선을(진출차수)로 나타낸다.
-
인접: 두 정점이 간서으로 적집 이어져 있다면 이 두 정점은 인접되어 있다고 한다.
-
자기루프: 정점에서 진출하는 간선이 다른정점을 거치지 않고 바로 자기자신에게 진입하는 경우 자기루프를 가졌다고 한다.
-
사이클: 한 정점에서 출발하여 다시 해당정점으로 돌아갈수 있다면 사이클이 있다고 한다. A,B,C가 있을때 A에서 시작해서 A에서 끝날때 즉, 시작 정점과 마지막 정점이 같은경우를 의미한다.
인접행렬
인접행렬은 정점들간의 인접함을 나타내는 행렬로 2차원 배열 모습을 하고있다. 만약 두 정점이 이어져 있다면 1 이어져있지 않다면 0으로 표시하는 일종의 표와 모습이 같다.
이러한 인접행렬은 두 정점 사이에 관계가 있는지 없는지 확인할때 유용하여 가장빠른길을 찾고자 할때 자주 쓰인다.
인접리스트
인접리스트는 각 정점이 어느 정점과 인접한지 리스트의 형태로 볼수있는 표현방식이다. 위의 인접행렬 표를 리스트로 나타내면 아래와 같다.
이러한 인접행렬은 연결가능한 모든 경우의 수를 저장하기에 메모리를 효율적으로 사용하고 싶으면 인접행렬대신 인접리스트를 사용한다.
Tree 🚩
Tree란?
트리는 일종에 가계도의 형태이다.
최상위에 루트노드를 가지고 있으며 루트노드 에서 아래로 뻗어나가 자식노드를 만들어나가 부모/자식 관계를 형성한다. 이때 이모습이 하나의 뿌리(루트노드) 에서 가지(자식노드)가 사방으로 뻗어나가는 모습과 같아 트리라고 불린다.
이때 A는 B의 부모노드가 되고 B는 A의 자식노드이며 D와E의 부모노드가 된다.
트리는 높이와 깊이(depth)를 잴수있다.
노드와 노드 사이에 거리를 level이라고 표현하고 root를 level1로 설정한다. 그렇게 가장 안쪽에 있는 노드까지의 level을 트리의 높이라 하고 특정노드 부터 시작해서 루트 까지의 level을 노드의 깊이라 한다.
위 사진과 같이 root에서 뻗어나가 큰 트리의 형태 안에 트리와 비슷한 형태를 갖춘 작은 트리를 서브 트리 라고한다.
Tree순회
-
전위순회: 루트에서 시작하여 루트를 기준으로 왼쪽의 노드를 우선 탐색하고 왼쪽 노드 탐색이 끝나면 오른쪽 노드를 탐색하는 순회방법
-
중위순회: 루트를 기준으로 제일 왼쪽 끝에있는 노드에서 순회를 시작하여 왼쪽 노드 탐색이 끝났으면 루트를 거쳐서 오른쪽 노드를 탐색하는 순회방법
-
후위순회: 중위순회와 똑같이 시작은 하지만 왼쪽 노드 탐색이 끝난후 루트를 거치지 않고 바로 오른쪽 노드를 탐색하고 제일 마지막에 루트를 탐색하는 순회방법
Binary Search Tree 🚩
자식 노드가 최대 2개로 이루어진 트리를 이진트리 라고한다.
이때 2개의 노드를 왼쪽 자식과 오른쪽 자식으로 나눠 부른다.
모든 왼쪽 자식은 루트나 부모보다 작은값이고 모든 오른쪽 자식은 루트나 부모보다 큰값을 가지고 있는데 이러한 특징을 가지고 있는 이진트리를 이진탐색트리(Binary Search Tree)라고 정의한다.
BFS / DFS 🚩
그래프의 탐색은 하나의 정점에서 시작하여 차례대로 모든 정점을 방문하는 것을 목적으로 삼는다.
BFS(너비 우선 탐색)
너비 우선 탐색은 가장 가까운 정점부터 탐색을 하는 방법이다.
주로 두 정점 사이의 최단 경로를 찾고자 할때 쓰인다.
만약 경로를 하나씩 전부 방문하는 방식으로 하게 되면 최악의 경우에는 모든 경로를 다 살펴 보게 될수도 있어 비 효율적이다.
DFS(깊이 우선 탐색)
깊이 우선 탐색은 너비 우선 탐색과는 반대로 루트에서 시작하여 하나의 경로를 전부 확인하고 그 다음 경로로 넘어간다.
너비 우선 탐색 보다 확실히 속도가 느리긴 하지만 모든 노드를 방문한다는 장점이 있다.
하루를 마치며👋
오늘은 고통스러운 하루였다... 자료구조.... 큐 와 스택은 아무것도 아니였다... 트리와 그래프 코플릿 문제풀때 무기력함을 느꼈다... 근데 아직 처음 접하는 부분이니 당연히 어려울꺼라 생각하여 위안을 삼아서 계속계속 풀어보면서 이해할수 있도록 해봐야겠다 ...! 그래도 다음주 ha가 기다리고 있는데 오늘 트리랑 그래프 접해보니 ha걱정이 태산이 되었다 ㅎ... 주말동안 부족한 부분 빡공 해야겠다 ! 🔥🔥🔥
