프로그래머스 데브코스 TIL - Day 5

 

✅ 학습 목차

- [Day 5] JavaScript 주요 문법 (5)

 

✅ 새롭게 학습한 부분

- 그래프

- 그래프의 구현/탐색

- 트리

- 트리의 탐색

---

그래프(Graph)

- 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조
- 정점 집합과 간선 집합으로 표현할 수 있다.

- 정점은 여러개의 간선을 가질 수 있다

- 순회는 DFS나 BFS로 이루어진다.

- 크게는 방향 그래프와 무방향 그래프로 나눌  수 있다

 

그래프의 구현 2가지

1. 인접 리스트

: 그래프를 표현하는 가장 일반적인 방법.

- 모든 정점을 인접 리스트에 저장한다. 각각의 정점에 인접한 정점들을 리스트로 표시.

- 정점의 번호를 배열의 인덱스로 하여 정점의 리스트에 쉽게 접근할 수 있다.

 

 1: [ 3, 2 ]
 2: [ 3, 1, 4, 5 ]
 3: [ 6, 4, 2, 1 ]
 4: [ 3, 2 ]
 5: [ 2 ]
 6: [ 3 ]

- 무방향 그래프(Undirected Graph)

간선은 두 번 저장된다. (양 쪽에 저장)

정점의 수: N, 간선의 수: E인 무방향 그래프의 경우

N개의 리스트, N개의 배열, 2E개의 노드가 필요하다.

 

 

2. 인접 행렬

- NxN 불린 행렬으로써 true라면 i -> j로의 간선이 있다는 뜻​​

- ​정점(노드)의 개수가 N인 그래프를 인접 행렬로 표현 한다면
- 간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요하다.
- 인접 리스트는 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있지만
- 인접 행렬에서는 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.

 

그래프의 탐색

 

1. 깊이 우선 탐색

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에

  해당 분기를 완벽하게 탐색하는 방법

- 모든 노드를 방문하고자 할 때 사용

 

 

2. 너비 우선 탐색 ​(BFS, Breadth-First Search)

- 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용

 

맨 처음 시작노드를 큐에 삽입하고 시작 노드를 방문 처리 해두고 시작한다.
큐에서 꺼낸 값을 탐색하여 인접한 노드를 큐에 삽입하고 방문처리를 하고
또 큐에서 꺼낸 값을 탐색하여 인접한 노드들을 큐에 삽입하고 방문 처리를 하는 과정을 반복한다.
그리고 큐에 값이 없을 경우(모든 방문을 마쳤을 경우) 종료된다.​​

---

트리(Tree)

방향그래프의 일종. 정점을 가르키는 간선이 하나밖에 없는 구조를 가지고 있다.
루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
루트에서 특정 정점으로 가는 경로는 유일하다.

 

이진트리(Binary Tree)

각 정점이 최대 2개의 자식을 가지는 트리

 

트리의 순회

이진 트리를 사용하여 순회를 할 수 있으며 순회의 종류는 3가지가 있다.

 

전위순회

: 부모노드-> 왼쪽 자식 노드 -> 오른쪽 자식 노드

 

중위순회

:왼쪽 자식 노드 -> 부모노드 -> 오른쪽 자식 노드

 

후위 순회

: 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드

 

---

✍느낀점

 

트리랑 그래프 자료구조를 처음으로 구현해봐서 익히는데 시간이 많이 걸렸다.

일단 오늘 배운 트리로 전위순회, 중위순회, 후위순회를 구현하는데에 있어서

재귀함수를 접하게 되었는데 아직 감이 다 잡히지는 않았다..😭 

과제 하다가 제대로 구현을 해놓고 this를 안적어서 안되는 코드인 줄 알고

다시 만들어보기도 하고..  가까스로 과제 1개는 완성 했으나 clone을 하는데

오류가 생겨서 몇시간 찾아보고 헤메기도 하고 시련이 많았던 하루였다..

하지만 전부 해결을 하고 커밋까지 해놓았다!🙌 그것으로 만족!

 

 

그래프(Graph)란