학습기록
DFS(Depth-First-search)
완전탐색하기위한 방법중하나며 이전에 그래프에대해 배웟을때 깊이에대해서 배웟다.
그래프에서 깊이가뭔지 살짝 끌어오자면 최상단노드에서 어떤루트에 가장 밑노드까지의 길이였다.
한 루트를그냥 가장깊이까지 전부 탐색하는거라보면됨. 그러면 모든요소를 한번훑을수있겠지?
DFS를 구현하기위해서는 보통스택을 사용하고 순환하기때문에(재귀)를이용한다.
그러면 DFS의 구현순서를 한번 살펴보자.
-
시작 노드를 스택에 넣고 [방문 처리]한다.
-
스택에 마지막으로 들어 온 노드에 방문하지 않은 인접 노드가 있는지 확인한다.
• 있다면, 방문하지 않은 인접 노드를 스택에 삽입하고 [방문 처리]한다.
• 없다면, 현재 노드(스택에 마지막으로 들어 온 노드)를 스택에서 추출한다.
항상 재확인과정이필요하다.
- 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다.
<DFS의 흐름을 나타낸그림>
BFS(Breadth-First Search)
DFS가 깊이위주였다면 이건 넓이위주로 탐색하는 방법론이다.
DFS와 다르게 모든간선의길이가 동일할떄 완전탐색하기위한방법이며 큐 자료구조를 활용해 구현한다.
(큐-> 들어오는대로나가는것)
BFS의 동작순서는
1. 시작 노드를 큐에 넣고 [방문 처리]한다.
- 큐에서 원소를 꺼내어 방문하지 않은 인접 노드가 있는지 확인한다.
• 있다면, 방문하지 않은 인접 노드를 큐에 모두 삽입하고 [방문 처리]한다.
- 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다.
DFS와 매우유사한데 큐에 넣는것만좀다르다.
DFS vs BFS?
BFS는 앞에서말햇듯 간선의길이가 동일한것부터 먼저탐색하기떄문에 DFS에비해 시간복잡도가 단축될수있는면이이있다. 그래서 최단거리를 구해야하는 문제에 많이 쓰게됨.
DFS는 호출을떠올리면된다.계속연산을해야하는경우는 DFS를 사용하자
다이나믹 프로그래밍(동적계획법)
요거는 문제를푸는방법론중하난데 재귀랑 비슷하다.
하나의문제를 작은단위로 바꾸어 해결하는 문제해결법이다.
동적계획법으로 해결하는 문제유형은 크게두가지가있는데
앞에서말한 재귀형태의문제
혹은 반복되는 작은부분문제를 계속해결해야하는경우
근데 이전에 피보나치수열에대해 작성했을때 메모이제이션에대해서 살짝 적었었다.
이게 DP(동적계획법)의 일부이다. 일부 결과값을 저장해 다시계산할필요없이 약간의 양을줄여주는것
일반적으로 동적계획법은 메모리를 늘리고 시간복잡도를 개선해준다. 따라서 이란 부하를 최대한 줄여주는것이중요하다.
수강인증샷
bfs문제풀이
강의상세페이지
https://fastcampus.co.kr/dev_online_upjscodingtest
#패스트캠퍼스 #패캠 #FASTCAMPUS #자바 #자바스크립트 #파이썬 #코딩테스트 #패스트캠퍼스후기
#코딩교육 #코딩자격증
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
