TIL 21.05.16

Jaemin Jung·2021년 5월 16일
0

Today I Learned

목록 보기
20/62
post-thumbnail

오늘한일

주말이지만 TIL을 적는다 목,금에 배웠던 자료구조에 대해서 아예 이해하질
못하고있어서 토요일엔 복습을 하였고, 오늘은 BFS/DFS를 이해 해봤지만,
역시 쉽진않다.

Achievement Goals

(이해한대로 작성하였기에 틀릴수도 있습니다. 계속 공부하며 수정해 나가겠습니다.)

-BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.

DFS / BFS

Graph를 탐색하는 방법은 대표적으로
깊이 우선 탐색 (Depth-First Search),
넓이 우선 탐색 (Breadth-First Search) 둘로 나뉜다.
줄여서 DFS / BFS라 하겠다.

DFS 깊이 우선 탐색

DFS는 Stack을 기반으로 Graph의 노드를 탐색하는 방법이다.

임의의 노드(Graph는 Root 노드가 없다.)에서 시작해서 자식 노드가 있으면,
그 자식 노드로 방문 그 자식노드에 또 자식 노드가 있으면 또 방문해서
끝까지 파고드는 방법이다.

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가
더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서
그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다.
출처: https://devuna.tistory.com/32 [튜나 개발일기]

DFS가 BFS보다 구현이 더 간단하고, 속도 자체는 BFS에 비해서 느리다.

BFS 너비 우선 탐색

BFS는 Queue을 기반으로 Graph의 노드를 탐색하는 방법이다.

임의의 노드(Graph는 Root 노드가 없다.)에서 시작해서 인접한 노드가 있으면,
그 인접한 노드를 차례로 방문, 가까운 정점에서부터 점점 멀어지는 탐색 방법이다.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.

BFS가 DFS보다 구현이 더 어렵다, 속도 자체는 DFS에 비해서 빠르다.

현재 상태

  • 주말에 많은걸 하려고 의지는 불타지만 쉽지가 않다.
  • 주말에 무엇을 할지 계획을 세워야 할듯

참고 사이트

https://devuna.tistory.com/32

profile
내가 보려고 쓰는 블로그

0개의 댓글