개발아 담하자

깊이 우선 탐색 (DFS; Depth First Search) 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘을 의미한다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행한다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색 하는 것이다. 빠르게 모든 경우의 수를 탐색하고자 할 때 사용한다. 스택 이나 재귀함수 로 구현한다. 아래는 DFS 탐색의 과정이다. 👇 아래는 DFS 를 C++ 로 구현한 코드이다. #include #include #include #include using namespace std; // dfs에 들어오면 '방문..

Floyd-Warshall (플로이드-워셜 알고리즘) 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. - '모든 정점' 에서 '모든 정점' 으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘 을 사용해야 한다. - 핵심 아이디어는 '거쳐가는 정점' 을 기준을 최단 거리를 구하는 것이다. - 기본적으로 다이나믹 프로그래밍(DP) 기술에 의거한다. - 최단 경로를 찾기에 좋은 알고리즘이다. 위와 같은 그래프가 존재한다고 가정할 때, 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 출력한다면 다음..