[데브코스 8일차] 그래프 탐색(DFS, BFS)과 그리디

💡 키워드

• DFS
• BFS
• 그리디
• 다익스트라 알고리즘
• 크루스칼 알고리즘

---

[1] 그래프 탐색 알고리즘

[1-1] DFS (깊이 우선 탐색)

가장 깊은 정점부터 탐색한다. 재귀 또는 스택으로 구현할 수 있다.

정점의 수가 V, 간선의 수가 E라고 할 때 시간복잡도는 O(V + E)

그림으로 보는 DFS

 

 

[1-2] BFS (너비 우선 탐색)

같은 깊이의 정점부터 탐색한다. 가장 가까운 정점부터 탐색한다는 점에서 그리디 + 큐 기반 알고리즘이다.

시간복잡도는 DFS와 같은 O(V + E).

그림으로 보는 BFS

 

[2] 그리디 알고리즘 (Greedy, 탐욕법)

당장 눈 앞에 보이는 최적해를 선택한다. 따라서 항상 최적해를 보장해주지는 않는다. 어느 정도의 최적해를 찾는 알고리즘. 코딩 테스트에서 특별한 알고리즘이 생각나지 않는다면, 구현 or 그리디 or 동적계획법(DP) 문제일 가능성이 크다. 직관이 필요한 알고리즘.

ex) 거스름돈 문제, 다익스트라(BFS + 그리디 + 큐), 크루스칼 알고리즘 등

 

[2-1] 거스름돈 문제

 

 

[2-2] 다익스트라(Dijkstra) 알고리즘

- 한 노드에서 다른 노드로 가는 경로를 찾는다. 즉 최단거리를 찾는 알고리즘.

- 기준이 한 노드이기 때문에 보통 1차원 배열 안에서 구현한다.

- 일종의 그리디 + BFS 알고리즘과 DP 알고리즘의 한 유형 (최단거리는 여러 개의 최단 거리로 이루어져 있다고 할 수 있기 때문)

그림으로 보는 다익스트라 알고리즘

출발 노드가 1이라고 하면

1) 노드 1에서 갈 수 있는 경로를 찾고 가장 저렴한 노드 4를 방문한다.

2) 노드 4에서 갈 수 있는 경로를 찾고 각 노드로 갈 수 있는 비용이 더 적다면 새로 갱신한다. 그리고 가장 저렴한 노드 2를 방문한다.

 

1) 노드 2에서 갱신할 노드는 없다.

2) 다시 노드 4로 가서 다음으로 저렴한 노드 5를 방문한다. 노드 5에서 갈 수 있는 경로를 찾고 각 노드로 갈 수 있는 비용이 더 적다면 새로 갱신한다. 그리고 가장 저렴한 노드 3을 방문한다.

노드 6에서 갱신할 노드는 없다. 프로그램이 종료된다.

 

[2-3] 크루스칼(Kruskal) 알고리즘

- 가장 적은 비용으로 모든 노드를 연결한다.

- 최소비용신장트리를 만들기 위한 대표적인 알고리즘

- 노드가 n개 일 때, 모든 노드를 연결하는 간선은 n-1개면 충분하다. 따라서 cycle이 발생하지 않도록 한다.

그림으로 보는 크루스칼 알고리즘

1. 간선의 비용이 가장 적은 순서부터 오름차순으로 정렬한다.

2. cycle이 발생하지 않는다면 연결(채택)한다.

3. cycle이 발생한다면 그 간선은 채택하지 않고 건너뛴다.

 

1

2

3

4

연결 완료

 

💡 오늘의 회고

오늘은 어제부터 구현하던 이진탐색트리를 계속해서 구현했다... 분할정복-재귀는 너무 어렵다 ㅠㅠ 강의에서 배운 내용은 비교적 연습을 많이 했던 DFS, BFS, 그리디 였기 때문에 강의 듣는 것은 좀 수월했지만... 프로그래머스 Lv3 입국심사를 풀지 못했다. 한 2시간 고민했는데 도저히 어떻게 풀지 해결방법이 떠오르지 않았음. 이 문제를 다시 푸는 날엔 어 왜이렇게 쉽지? 하면서 푸는 내가 되었으면 좋겠다. 저번주에 밀리고 밀린 것들을 이제야 거의 끝냈다. 이번 주부터는 정말 진도를 좀 더 빨리 빼야겠다. 아무리 생각해봐도 지금 나는 버리고 있는 시간이 너무 많은 것 같다. (데브코스가 버리고 있는 시간이라는 것 절대아님!!!) 매일 13시부터 19시까지 코어타임을 진행하는데, 코어타임을 너무 알차게 사용하고 있지 못하는 것 같다. 2주차에 접어들면서 슬슬 시스템 자체에는 적응을 해서 다행이긴 한데... 코어타임을 더 알차게 사용할 수 있도록 해야겠음. 내일모레부터 (너무너무너무 좋은) 우리 팀원들과 <모던 자바스크립트 딥 다이브> 스터디를 시작하려고 한다. 코어타임에는 모자딥다(모던 자바스크립트 딥 다이브 라는 뜻) 공부와 강의를 보면서 알고리즘 문제를 풀면 더 알차게 사용할 수 있을 것 같다. 지금까지 코어타임동안 내가 따로하는 공부들을 해왔는데 정말 잘못 된 것 같음. 데브코스를 하게된 목적이 "함께 성장하는 것" 이었다. 코어타임동안에는 함께 성장할 수 있는 공부를 하자. 또 내 개인 공부는 밤 늦게 혼자 할 때가 더 잘되는 것 같다. 휴.... 이렇게 점점 최적화(산업공학과 특)를 해 가야겠다. 그리고 다시 말하지만 이번 주부터는 함수형 프로그래밍 강의 진짜 열심히 들어야 한다. 부지런히 부지런히 달리자!!!