2024-09-15

공부

• 코테를 위해 알고리즘 공부를 꾸준히 하고 있는데 DFS와 BFS가 정말 어려운 것 같다.. 그래도 내가 이해한 것에 대해 정리를 해보겠다.

  우선 DFS와 BFS는 탐색 알고리즘 중 하나이다. 탐색 알고리즘은 데이터 구조 안에서 특정한 데이터를 찾는 방법을 정의한 알고리즘이다.

  그렇다면 탐색 알고리즘이 필요한 이유는 뭘까?
  바로 빠른 검색, 정확한 검색, 효율적인 메모리 사용이 있다.

  그리고 DFS와 BFS를 공부해야 하는 이유는 뭘까?
  탐색 알고리즘은 그래프를 탐색하는건데 그냥 탐색하는 되는 거 아닌가? 라고 생각할 수 있다. 이런 의문에 대해 아래와 같은 질문을 할 수 있을 것 같다.

  (1) 한 정점에서 다른 정점으로 연결된 건 어떻게 알 수 있을까?
  (2) 위의 알고리즘이 없다면 직접 효율적인 코드를 짜야 할텐데 가능한가? 그리고 정확도는 장담할 수 있을까?

  -> 그렇다 그래프를 탐색하기 위해서는 어느정도의 효율성과 체계성이 필요하다.

깊이 우선 탐색(Depth-First Search, DFS)

깊이 우선 탐색(Depth-First Search, DFS)는 그래프나 트리 구조에서 깊은 부분까지 탐색하는 방법으로 스택 자료구조를 이용하며, 재귀 호출로 구현할 수 있다.
원

• 장점
  코드가 직관적이고 비교적 구현하기 쉽다.
  -> 일정 행동을 계속 반복하기 때문에 재귀함수로 비교적 간단하게 코드를 구현할 수 있다.

• 단점
  (1)깊이가 깊어지면 메모리 비용을 예측하기 어렵다.
  -> 깊이가 깊어질수록 함수가 하나씩 쌓이는 구조이기 때문에 스택 메모리가 지나치게 커질 수 있다.

  (2)최단 경로를 알 수 없다.

  

  DFS의 원리

  *스택 (LIFO)
  push() : 배열 끝에 새로운 요소 추가 및 새로운 길이 반환
  pop(): 배열의 마지막 요소 제거 및 그 요소 반환

  A B D E F C G H I J 순으로 깊이를 기준으로 먼저 탐색하는 알고리즘입니다.
  위 그림을 기준으로 DFS의 원리를 확인해보도록 하겠습니다.

  (1) A를 시작 정점으로, 스택에 A를 넣습니다. (스택 : A)
  (2) A를 뽑으며, 이와 연결된 정점 B, C를 스택에 넣습니다. (스택 : B, C)
  (3) 스택의 가장 위에 있는 B를 뽑고, B와 연결된 D를 스택에 넣습니다. (스택 : C, D)
  (4) 스택의 가장 위에 있는 D를 뽑고, D와 연결된 E, F를 스택에 넣습니다. (스택 : C, E, F)
  (5) 스택의 가장 위에 있는 F를 뽑습니다. F와 연결된 노드는 없으므로, 더 이상 추가하지 않습니다. (스택 : C, E)
  ...
  → 이와 같이 스택을 통해 깊이 우선으로 탐색할 수 있습니다.
  한 노드를 기준으로 가능한 깊이를 우선적으로 탐색하며,
  더 이상 방문할 노드가 없다면 이전 노드로 돌아가 다음 노드를 탐색합니다.

  이렇게 스택의 최상단 노드에서 탐색을 계속하다가
  더 이상 방문할 노드가 없을 때 이전 단계로 돌아가는 것이 DFS의 특징입니다.

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

너비 우선 탐색(Breadth-First Search, BFS)는 그래프나 트리 구조에서 가까운 노드부터 탐색하는 방법으로 큐 자료구조를 이용한다.

• 장점
  (1) 비교적 효율적인 운영이 가능하고 시간/공간 복잡도 면에서 안정적이다.
  (2) 최단 경로를 구할 수 있다.

• 단점
  (1) 구현이 비교적 까다롭다
  (2) 모든 지점을 탐색한다는 가정하에 큐에 메모리가 준비되어 있어야 한다.

  

BFS의 원리

*큐 (FIFO)
push() : 배열 끝에 새로운 요소 추가 및 새로운 길이 반환
shift() : 배열의 첫 번째 요소를 제거하고, 그 요소를 반환

A B C D G H I E F J 순으로 너비를 기준으로 먼저 탐색하는 알고리즘입니다.
위 그림을 기준으로 BFS의 원리를 확인해보도록 하겠습니다.

(1) A를 시작 정점으로, 큐에 A를 넣습니다. (큐 : A)
(2) A를 뽑으며, 이와 연결된 정점 B, C를 큐에 넣습니다. (큐 : B, C)
(3) 큐의 가장 앞에 있는 B를 뽑고, B와 연결된 D를 큐에 넣습니다. (큐 : C, D)
(4) 큐의 가장 앞에 있는 C를 뽑고, C와 연결된 G, H, I를 큐에 넣습니다. (큐 : D, G, H, I)
(5) 큐의 가장 앞에 있는 D를 뽑고, D와 연결된 E, F를 큐에 넣습니다. (큐 : G, H, I, E, F)
...
→ 이와 같이 큐를 통해 단계별로 탐색할 수 있습니다.

DFS와 BFS에 대해 이렇게 정리는 했지만 문제를 풀 때 사용하는게 어렵다🥲

운동

• 요즘 들어서 가끔 한번씩 드는 생각이 있다. 원래 운동을 하는 것이 너무 좋고 뿌듯했는데 한번씩 운동을 쉬고 싶은 날이 있는데 아직까지는 게을러지지 않도록 쉬려는 유혹을 뿌리치고 있지만 가끔 힘들 때가 있다. 🥲

취업

기타