deulee의 개발 노트

문제 방향그래프와 시작점이 정해지고 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성해야 한다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 > E >> S; for (int i = 0; i > U >> V >> W; varr[U].push_back(std::make_pair(V, W)); } for (int i = 1; i

알고리즘/문제 2023. 5. 22. 17:04

문제 자연수 A를 B번 곱하는 거듭제곱을 구하는 문제이다. 이때 구하려는 수가 커지는 것을 방지해 C를 나눈 나머지를 구하는 프로그램을 작성한다. A^B 입력 A, B, C가 차례대로 주어진다. 입력 예제 10 11 12 예제 출력 4 문제 해결 어디서 힌트를 얻을 수 있을까? 문제에서는 A를 B번 곱한 수를 구하는 것이라고 했다. 이 말을 다르게 생각하면 A는 B의 거듭제곱이 되는 것이다. 거듭제곱은 수열의 빠른 합과 같은 맥락으로 풀 수 있다. 즉, B를 계속 반으로 나눈 값으로 문제를 푸는 것이다. 이렇게 된다면 문제는 다음과 같이 정의할 수 있다. A^(B/2) * A^(B/2) ↓ K = A^(B/2) ↓ K * K 위와 같이 바꿀 수 있는 것이다. 그러면 홀수의 경우는 어떨까? 홀수의 경우에는..

알고리즘/문제 2023. 5. 22. 00:18

문제 방향성이 없는 간선이 주어지고 정점 1부터 정점 N까지 도착하는 최단 경로를 구하는 것이다. 이때 정점 X, Y를 경유하는 최단 경로를 구해야 하는 문제이다. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 nDis) { disArr[flag][nNode] = nDis; pqarr.push(std::make_pair(nNode, nDis)); } } } } void init(void) { for (int i = 0; i > N >> M; for (int i = 0; i < M;..

알고리즘/문제 2023. 5. 21. 20:36

BFS는 가중치가 있는 간선이 있는 그래프에서는 최단 거리 알고리즘으로써 사용될 수 없다. 그 이유는 BFS는 방문한 순서대로 동작을 하게 되기 때문이다. 그렇기 때문에 다음과 같은 상황에서 전혀 사용할 수 없는 것이다. 시작점이 A라고 가정해보자. 시작점 A를 방문하게 되었을 때 BFS 알고리즘을 이용하게 된다면 (2, B)와 (12, C)를 '그냥 큐'에 넣게 될 것이다. 그리고 나서 D를 방문하게 되고 알고리즘은 종료를 하게 될 것이다. 이렇게 될 경우 BFS 알고리즘 입장에서 A에서 C까지의 최단 경로가 12가 되는 것이다. 실제로는 2 + 4 + 3 = 9 인데도 말이다. 즉, A에서 C까지의 최단 경로는 A to C가 아니라 A to B to D to C가 되는 것이다. 이러한 상황에서 BFS..

알고리즘/이론 2023. 5. 21. 20:20

다익스트라(Dijkstra) 알고리즘은 그래프 이론을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘이다. 이 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 하지만 이 때 음의 간선을 포함하고 있는 경우 이 알고리즘은 사용할 수 없다는 점을 기억하고 이 글을 읽어보도록 하자. 하지만 애초에 다익스트라(Dijkstra) 알고리즘 BFS(너비 우선 탐색)을 기반으로 만들어진 알고리즘이기 때문에 BFS와 유사한 점이 많이 있다. 하지만 BFS는 가중치가 있는 그래프, 즉 각 간선마다 비용이 정해져 있는 경우 사용할 수 없다. 그 이유는 너비 우선 탐색은 발견한 순서부터 탐색을 시작하기 때문이다. 이 이유는 다른 장에서 따로 설명하도록 하겠..

알고리즘/이론 2023. 5. 21. 20:12

문제 N개의 정점이 있고 각 정점에서 특정 점정 X가 정해진다. 이때 각 정점에서 i를 방문하고 다시 자기 자신의 정점으로 돌아오는 최소 길이를 구한 뒤 가장 많은 비용을 소비하는 정점을 구하는 문제이다. 입력 첫째 줄에 N(1 tmpDis + nextDis && nextNode != Node) { disArr[flag][nextNode] = tmpDis + nextDis; pqarr.push(std::make_pair(nextNode, disArr[flag][nextNode])); } } } } void init(void) { for (int i = 0; i < 1001; i++) { disArr[0][i] = INF; disArr[1][i] = INF; } } int main(void) { int N..

알고리즘/문제 2023. 5. 21. 18:02

우선 선형 시간안에 트리의 지름을 구하는 방법은 다음과 같다. 트리에서 임의의 정점 X를 정한다. 정점 X에서 가장 먼 정점 Y를 구한다. 정점 Y에서 가장 먼 정점 Z를 구한다. 즉, 트리의 지름은 정점 Y와 정점 Z 사이의 거리를 의미한다. 이를 증명하는 방법은 다음과 같다. 증명 만약 트리에서 정점 U와 정점 V를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 X를 정하고, X에서 가장 먼 정점 Y를 찾았을 때, 아래와 같이 경우를 만들 수 있다. X가 U 혹은 V인경우 Y가 U 혹은 V인경우 X, Y, U, V가 서로 다른 경우 이 경우 1, 2번은 무조건 올바르게 작동할 수 밖에 없다. 그야 DFS 알고리즘에 의해서 당연히 성립될 수 밖에 없다. 그럼 문제는 3번의 경우이다. 3번의 ..

알고리즘/이론 2023. 5. 20. 18:33

문제 설명 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리를 구하는 프로그램을 작성해라. 입력 트리가 입력으로 주어진다. 첫 번째 줄에는 정점의 개수 V가 주어진다. (2 V; for (int i = 0; i > node; int x, y; while (1) { std::cin >> x; if (x == -1) break ; std::cin >> y; varr[node].push_back({x, y}); } } dfs(1, 0); std::memset(cache, 0, sizeof(cache)); maxDis = 0; dfs(maxNode, 0); std::cout

알고리즘/문제 2023. 5. 20. 18:32