👀Today I LearnPermalink

1. 깊이 우선 탐색(DFS)Permalink

• DFS는 한 노드를 방문하면 최대한 깊이 내려간 후, 더 이상 갈 곳이 없으면 다시 돌아오는 방식으로 탐색하는 알고리즘
• 주로 재귀(Recursion) 또는 스택(Stack) 을 이용하여 구현

DFS의 특징Permalink

• 한 방향으로 깊이 탐색 후 백트래킹 (되돌아가기)
• 재귀 함수 또는 스택을 이용한 구현
• 그래프의 모든 정점을 방문하는 데 사용됴됨
• 최단 경로 탐색에는 부적합 (너비 우선 탐색이 더 적합)
• 트리나 그래프에서 경로를 찾거나 특정 패턴을 탐색할 때 유용

DFS의 동작 방식Permalink

• 다음과 같은 그래프를 가정

     1
    /|\
    2 3 4
    |   |
    5   7
    |
    6
  

  1. 첫 번째 노드(1)부터 시작
  2. 방문할 수 있는 한 계속 내려감 (DFS 특성)
  3. 더 이상 갈 곳이 없으면 백트래킹하여 다른 길 탐색

DFS의 구현 : 재귀Permalink

# 그래프를 인접 리스트 방식으로 표현
graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [],
    4: [7],
    5: [],
    6: [],
    7: []
}

# DFS 구현 (재귀 방식)
def dfs_recursive(node, visited):
    if node not in visited:
        visited.append(node)
        print(node, end=' ')
        for neighbor in graph[node]:
            dfs_recursive(neighbor, visited)

# 실행
visited = []
dfs_recursive(1, visited)

DFS의 구현 : 스택Permalink

# DFS 구현 (스택 사용)
def dfs_stack(start):
    stack = [start]
    visited = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            print(node, end=' ')
            stack.extend(reversed(graph[node]))  # 스택에서 뒤집어서 넣어야 순서 유지

# 실행
dfs_stack(1)

2. 너비 우선 탐색(BFS)Permalink

• BFS는 현재 방문한 노드에서 인접한 노드들을 먼저 모두 방문한 후, 다음 깊이의 노드들을 방문하는 탐색 방법
• 주로 큐(Queue) 를 사용하여 구현

BFS의 특징Permalink

• 가까운 노드부터 탐색하는 방식
• 큐를 이용한 구현
• 최단 경로 탐색에 적합
• DFS보다 메모리 사용량이 많을 수 있음
• 레벨별 탐색이 필요할 때 유용함

BFS의 동작 방식Permalink

• 위에서 사용한 동일한 그래프에서 탐색을 수행

  1. 시작 노드(1)에서 인접한 모든 노드(2, 3, 4)를 먼저 방문
  2. 다음 깊이의 노드(5, 7)를 방문
  3. 계속해서 큐에서 꺼내며 탐색 진행

BFS의 구현 : 큐Permalink

from collections import deque

# BFS 구현 (큐 사용)
def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            print(node, end=' ')
            queue.extend(graph[node])

# 실행
bfs(1)

3. DFS vs BFS 비교Permalink

실행 순서 차이 예시Permalink

• DFS 실행 결과: 1 → 2 → 5 → 6 → 3 → 4 → 7

• BFS 실행 결과: 1 → 2 → 3 → 4 → 5 → 7 → 6

4. DFS/BFS 활용 예시Permalink

📌DFS가 유용한 경우Permalink

• 백트래킹 (예: N-Queen 문제, 순열 생성)
• 모든 경로 탐색 (예: 미로 찾기, 게임 맵 탐색)
• 트리 구조 탐색 (예: 이진 트리 순회)

📌BFS가 유용한 경우Permalink

• 최단 거리 탐색 (예: 최단 경로 문제, 다익스트라 알고리즘)
• 네트워크 탐색 (예: SNS 친구 추천, 웹 크롤링)
• 망 분할 탐색 (예: 전염병 확산 시뮬레이션)

5. 결론Permalink

• DFS와 BFS는 그래프 탐색에서 매우 중요한 알고리즘
• 요약
  • DFS: 깊이 우선 탐색, 백트래킹 활용, 스택/재귀 구현
  • BFS: 너비 우선 탐색, 최단 거리 탐색에 적합, 큐 구현

💡Today I ThoughtPermalink

오늘의 체크리스트Permalink

• 알고리즘 코드카타 311-315
• SQL 코드카타 104
• AI 모델 활용 2주차 강의 듣기
• 딥러닝 복습
• TIL 작성

회고Permalink

  오늘 하루도 알차게 마무리! 어제 스탠다드반에서 딥러닝을 다뤄서 다시 공부했는데, 모르는 개념이 아직도 많이 넘친다. 딥러닝 공부는 계속 필요할 것 같다. 스탠다드반에서 과제주면 꼬박꼬박 하면서 또 성장해야지🫠