(10주차) DFS&BFS, 그리디 알고리즘, 최소 스패닝 트리

DFS & BFS

  • 경로 찾기 문제의 상황에 따라 DFS와 BFS를 그래프 알고리즘으로 사용할 수 있습니다.

  • 그래프는 꼭짓점을 연결하는 노드와 가장자리로 구성된 데이터 구조이며 그래프를 순회한다는 것은 꼭짓점에서 시작하여 모든 꼭짓점을 순서대로 한 번 방문하는 것을 의미합니다.

  • 그래프 순회를 위한 두 알고리즘 방문한 노드검사를 받아야 합니다.

    (활성화하지 않으면 무한 루프의 위험)


깊이 우선 탐색(DFS)

  • 루트 노드(또는 임의의 노드)에서 시작하여 다음 분기로 이동하기 전에 모든 분기를 통과(미로와 유사)
  • 스택 또는 재귀 함수(재귀 알고리즘의 형태로)로 구현
  • 모든 경로를 방문해야 하는 경우적합
  • 시간 복잡도(V는 정점, E는 에지)
    • 인접 행렬: O(V^2)
    • 이웃 목록: O(V+E)

너비 우선 탐색(BFS)

  • 따라서 먼저 루트 노드(또는 임의의 노드)에서 이웃 노드로 검색합니다.

  • 예어(노드 주변에서 검색해야 하기 때문에) → 선입선출(FIFO) 원칙에 따라 검색으로 구현
  • 최소 비용우선권이 주어질 때 적합
  • 주로 두 노드 사이의 최단 경로필요한 것을 찾기 위해
  • 재귀적으로 작업
  • 시간적 복잡성
    • 인접 행렬: O(V^2)
    • 이웃 목록: O(V+E)

그리디 알고리즘

  • 그리디 알고리즘
  • 문제 해결 과정에서 우리는 언제라도 답에 도달하는 것이 최적인 방식으로 진행합니다.

  • 문제의 본질이 동일하고 동일한 전략을 반복적으로 사용할 수 있는 경우 적용
    • 이전 결정이 후속 결정에 영향을 미치지 않는 경우
    • 최종 솔루션이 하위 문제에 대한 솔루션과 동일한 조건인 경우
  • 장점: 다른 최적 솔루션 계산 알고리즘에 비해 저렴한 비용(빠름)
  • 단점: 최적의 가치를 찾는 순간이기 때문에 항상 최적의 솔루션을 찾는 것은 불가능합니다.