알고리즘 풀어주는 블로그

완전 탐색 그래프를 탐색하는 방법중에 brute-force 라는 방법이 있습니다. Brute(무식한) + Force(힘) 라는 의미로 극단적으로 말하자면 무식하게 모든 자료를 찾아본다는 방법입니다. 그 중에 그래프의 전체 노드를 탐색하는 것을 완전 탐색이라고 합니다. 완전 탐색의 종류로는 대표적으로 깊이 우선 탐색(dfs), 너비 우선 탐색(bfs) 가 있습니다. 깊이 우선 탐색 (Depth First Search) 깊이 우선 탐색(이하 DFS)는 루트 노드에서 탐색을 시작하여 리프 노드의 끝까지 탐색을 하는 방법입니다. 그 다음 리프 노드에서 끝이 나면 바로 윗 레벨의 다른 분기의 다른 리프 노드의 끝까지 탐색을 이어나갑니다. 즉, 가장 깊은 노드 = 리프 노드 = 가장 최대 레벨의 노드 를 우선적으로..

최단경로 란? 그래프는 보통 정점(V, vertex)와 간선(E, edge)로 이루어져 있습니다. 여기서 정점은 노드(Node)로 표현하기도 합니다. 그 중 정점과 정점사이를 잇는 가장 짧은 거리를 최단 경로라고 합니다. 가중치 유무에 따라 일반적으로 최단 경로가 의미하는 값이 달라집니다. 여기서 가중치란 서로 연결된 정점과 정점을 잇게 할 때, 소모되는 비용입니다. 코딩테스트 문제에서는 흔히 길을 이동하는 데 필요한 연료, 소비되는 시간 등으로 표현됩니다. 가중치가 없는 그래프 : 가장 길이가 짧은 거리 가중치가 있는 그래프 : 가장 적은 비용이 드는 거리 1) 가중치가 없는 그래프 가중치가 없는 그래프에서 (1 , 5) 사이의 최단 경로는 1로 [1 -> 5]로 바로 이어지는 경로입니다. 1에서 5까..