♣ 데이크스트라 알고리즘 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘으로, 컴퓨터 과학자 에츠허르 데이크스트라가 고안했다. 데이크스트라 알고리즘은 변형이 많은데, 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 것이지만 보다 일반적인 변형은 한 꼭짓점을 source 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 최단경로트리 알고리즘이다. 예를 들어 그래프에서 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면 데이크스트라 알고리즘을 통해 두 도시 사이의 최단 경로를 찾을 수 있다. 이러한 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용된다. a와 b 사이의 최단 경로를 찾은 데이크스트라 알고리즘이다. 가장 낮은 값을 가진..

♣ DFS(Depth-First-Search, 깊이우선탐색)트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘을 의미한다. 깊이를 우선시하여 모든 경우의 수를 탐색하며, 주로 반복문이나 재귀문을 활용하여 구현한다.  ♣ DFS 탐색과정 1. 현재 노드를 방문한 것으로 표시함2. 방문 표시가 되어 있지 않은 각각의 인접한 정점을 탐색함3. 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking)함4. 모든 정점을 방문할 때까지 과정을 반복함 0번 노드에서 탐색을 시작하면서 자식 노드인 1과 2를 탐색할 수 있다. 1번 노드를 탐색하였다고 결정하면 1번 노드의 자식들까지 완벽하게 탐색하기 전까지 2번 노드는..

♣ 문제 ♣ 문제 이해 이전 글인 너비우선탐색을 이용하여 해결할 수 있는 문제이다. https://jy-deeplearning.tistory.com/72 BFS(너비 우선 탐색, 백준 알고리즘 16953번) ♣ 문제 ♣ 문제 이해 주어진 정수 A를 정수 B로 바꾸는 문제로, A*2를 하거나 str(A)+'1'을 해서 숫자를 바꿔간다. 첫 번째 예제를 보면 2 -> 4 -> 8 -> 81 -> 162 루트를 통해서 162를 만들 수 있고, 4번의 숫 jy-deeplearning.tistory.com 주어진 트리의 루트는 1이고, 1부터 시작하여 노드들이 연결된다. 이때 각 노드의 부모를 출력하는 문제이다. 위의 첫 번째 예제를 보면 트리는 아래와 같다. 노드 1을 제외하고 2부터 마지막 7까지의 부모 노드..

♣ 문제 ♣ 문제 이해 주어진 정수 A를 정수 B로 바꾸는 문제로, A*2를 하거나 str(A)+'1'을 해서 숫자를 바꿔간다. 첫 번째 예제를 보면 2 -> 4 -> 8 -> 81 -> 162 루트를 통해서 162를 만들 수 있고, 4번의 숫자 변화 끝에 답을 얻은 것이므로 4+1 = 5 를 프린트한다.  반면 두 번째 예제(4, 42)를 보면 위의 그림과 같아서 4를 42로 만들 수 있는 경우가 없기 때문에 -1을 출력해야 한다.   ♣ 문제 해결 방법처음에는 주어진 오리지널 숫자를 2배 하거나 뒤에 1을 덧붙이는 수를 모두 리스트에 넣어서 조건을 따지려고 했는데 너무 복잡하게 느껴졌다. 그래서 오리지널 숫자는 그냥 두고 원하는 결과인 숫자로부터 따지기로 했다.  예를 들어 첫 번째 예제(2, 162..

♣ 문제 ♣ 문제 이해 n은 총 노드의 수, m은 리프 노드의 수를 가리킨다. m개의 리프노드는 부모 노드와는 연결되어 있어야 하지만 자식 노드는 갖지 않는다. 따라서 부모와 연결된 노선만 존재한다. 즉 n개의 노드가 주어지고, 리프 노드가 몇 개인지를 고려하여 노드들 사이의 노선을 완성하여 출력하면 되는 것이다. 예를 들어 예제가 4 2 일 때 예제 출력이 0 1, 1 2, 2 3이다. 위의 출력은 수많은 답 중 하나일 뿐이다(이 문제에는 스페셜 저지가 적용된다. 출력된 노선을 노드 사이에 그리면 0, 3 노드가 리프 노드이고, 1과 2는 그 외의 노드가 된다. 답이 이렇게 나와도 된다. 위의 그림에서는 1과 2가 리프노드이고 0과 2는 그 외의 노드가 되는 것이다. ♣ 해결 방법 처음에는 답이 하나만..

♣ 신장트리 연결 그래프의 부분 그래프로서, 그래프의 모든 노드 간선의 부분 집합으로 구성되는 트리 모든 노드는 적어도 하나의 간선에 연결되어 있다. n개의 노드(정점)을 가지는 그래프가 있다면, n개의 정점을 모두 연결할 수 있는 n-1 개의 엣지(간선)으로 이뤄진 부분 그래프들을 신장트리라고 한다. 즉 최소의 간선 수는 n-1이다. ♣ 참고 자료 https://limecoding.tistory.com/123 신장 트리(Spanning Tree) 신장 트리란?(What is a Spanning Tree?) 앞서 포스팅에서 깊이 우선 탐색과 너비 우선 탐색에 대해 다루었다. 연결 그래프 G = (V, E)에 대해서 깊이 우선 탐색이나 너비 우선 탐색을 하게 되면 정점들을 limecoding.tistory..