📌 너비우선탐색BFS/깊이우선탐색DFS
(1) 너비우선탐색 BFS
참고한 사이트 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
https://m.blog.naver.com/occidere/220923695595
Breadth-First Search 그래프 탐색 알고리즘.
그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.
=> 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘. 즉, 현재 정점과 연결된 정점들에 대해 우선적으로 넓게 탐색하는 방식!
흠... level order 트리탐색 아녀 이거
깊이
BFS의 특징
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용.
- 재귀적으로 동작하지 않는다.
- 그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사해야 하지만, BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다. FIFO 원칙으로 탐색.
(2) 깊이우선탐색 DFS
참고한 사이트 :
https://hudi.blog/dfs-bfs/
https://m.blog.naver.com/occidere/220923695595
Depth First Search 그래프탐색알고리즘. 최대한 깊은정점부터 탐색한다.
루트 노드에서 시작하여 다른 분기로 넘어가기 전, 현재 탐색 중인 분기를 완벽하게 탐색하는 방식. 가장 깊은 노드까지 도달하였을 때 탐색한 경로를 역추적하여 되돌아나오기 위해 스택을 사용한다. 또한 이미 방문한 노드를 다시 방문하지 않기 위해 방문한 노드를 따로 저장해야 한다. 이를 '방문처리'라고 한다.
DFS의 특징
- 스택으로 구현한다.
- 시작정점에서 깊은 것부터 찾음.
-시간복잡도는 BFS와 동일하다.
동작 순서
- 루트 노드를 스택에 넣고 방문처리 한다.
- 스택 최상단 노드의 인접 노드 중 방문하지 않은 노드 하나를 스택에 넣고 방문처리 한다. 만약 인접노드를 모두 방문한 경우 스택을 pop한다.
- 2단계를 더 이상 수행할 수 없을 때까지(스택이 빌 때까지) 반복한다.
DFS 실습 하기
(1) 프로그래머스 lv3. 여행경로
https://school.programmers.co.kr/learn/courses/30/lessons/43164
(2) 프로그래머스 lv3. 네트워크
https://school.programmers.co.kr/learn/courses/30/lessons/43162
📌 그리디 알고리즘
Greedy
매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘. 최적해를 보장해주지 않는다.
그리디 알고리즘의 특징
- 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많음
- 크루스칼, 다익스트라 알고리즘 등에 사용됨
- 직관적인 문제 풀이에 적합
- ex) 동전반환문제: 거스름돈을 최대한 큰 단위로 거슬러주는 문제
그리디 실습하기
프로그래머스 lv2. 큰 수 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/42883
