[알고리즘/파이썬] DFS와 BFS의 개념과 구현

그래프 탐색 알고리즘먼저 그래프 탐색 알고리즘이란,여러 개체들이 연결되어 있는 자료구조인 그래프에서 특정 개체를 탐색하고 찾기 위한 알고리즘이다. 그래프 탐색 알고리즘 대표적인 유형이 DFS(깊이우선탐색)와 BFS(너비우선탐색)이다. 드라마 정주행을 비유해봤을 때, 한 드라마를 처음부터 끝까지 몰아봐야 하는 유형이 DFS이고, 모든 드라마 여러 개를 하나씩 본방사수하면서 챙겨봐야 하는 유형이 BFS이다.  대표적인 그래프 탐색 알고리즘 유형경로탐색 유형 : 최소거리 구하기, 최단 시간 구하기네트워크 유형 : 여러 개체들이 주어진 상태에서 연결되어 있는 그룹의 갯수를 구하기, 그룹 안에서 개체들이 연결되어 있는지의 여부 판단조합 유형 : 여러가지의 조합을 전부 만들고 비교해보기  DFS/BFS 구현 방법우..

• format_list_bulleted Computer Science/Algorithm
• · 2024. 8. 9.
• textsms

[알고리즘/파이썬] 위상 정렬(Topology Sort)은 무엇일까?

😮 위상 정렬이란?순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘입니다. 즉, 그래프의 흐름(순차적인 그래프)이 있고 다양한 조건들이 서로 얽혀있을 때, 정확히 1열로 그래프의 각 노드를 나열할 수 있도록 하는 것이 위상 정렬입니다. 예를 들어보겠습니다.위 그림과 같이 총 3개의 과목이 있다고 가정해봅시다. 세 과목을 모두 듣기 위해서는 `자료구조 -> 알고리즘 -> 고급 알고리즘` 순서로 과목을 들어야 합니다.  만약 `자료구조 -> 고급 알고리즘 -> 알고리즘` 순서로 과목을 듣는다면, 해당 순서는 올바른 학습 순서가 아닙니다. 위상 정렬은 다음과 같은 개념이 필요합니다.진입차수 : 특정한 노드가 있을 때 그 노드로 들어오는 다른 노드의 갯수를 의미합니..

• format_list_bulleted Computer Science/Algorithm
• · 2024. 8. 1.
• textsms