deulee의 개발 노트

문제 사이클이 없는 무방향 그래프 트리(tree)가 주어질 때 트리의 지름을 구하는 문제다. 입력 첫째 줄에 노드의 개수 N (1 N; int X, Y, C; int ret; while (1) { if (!(std::cin >> X >> Y >> C)) break ; varr[X].push_back(P(Y, C)); varr[Y].push_back(P(X, C)); } dfs(1, 0); std::memset(cache, 0, sizeof(cache)); maxDis = 0; dfs(maxNode, 0); std::cout

알고리즘/문제 2023. 5. 24. 18:56

문제 삼각형이 주어지고 위에서 아래로 내려오는데, 이때 그냥 내려오거나 오른쪽 대각선으로 내려가야만 한다. 이런 상황에서 합이 최대가 되는 경로에 있는 수의 합을 출력해라. 입력 첫째 줄에 삼각형의 크기 n(1 > N; for (int i = 0; i > board[i][j]; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cache[i][j] = -1; } } std::cout

알고리즘/문제 2023. 5. 24. 17:56

문제 흔히 우리가 사용하는 수식은 중위 표기법으로 (A+B) 사용되고 있으며 이를 후위 표기법(AB+)으로 바꾸는 문제이다. 이는 연산자가 피연산자 뒤에 위치하는 방법이다. 이를 실행하는 방법은 다음과 같다. 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. A+B*C == (A+(B*C)) 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨준다. (A+(B*C)) == (A+BC*) == ABC*+ 입력 첫째 줄에 중위 표기식이 주어진다. 단, 알파벳 대문자로만 이루어져 있으며 연산자가 가장 앞에 오거나 곱셈이 생략되는 경우는 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, ) 로만 이루어져 있으며, 길이는 100을 넘지 않는다. 예제 입력 A*(B+C) 예제 출력 ABC+* 문제 ..

알고리즘/문제 2023. 5. 24. 17:29

문제 정점 N개와 M개의 간선이 주어진다. A번째 정점에서 B번째 정점까지 도달하는 데 드는 최소 비용을 출력하라. 입력 첫째 줄에 N(1 M; for (int i = 0; i > X >> Y >> C; varr[X].push_back(P(Y, C)); } for (int i = 0; i > S >> D; Dijkstra(S); std::cout

알고리즘/문제 2023. 5. 23. 15:19

문제 N개의 정점이 있고 M개의 방향성이 없는 간선과 W개의 방향성이 있는 그래프가 주어진다. 이때 W는 음수의 가중치를 가지고 있다. 어느 시작점이든 출발을 했을 때보다 시간이 더 적은 경우가 있으면 "YES" 없으면 "NO"를 출력하는 문제이다. 입력 첫 번째 줄에는 테스트케이스의 수 T가 주어진다. 두 번째 줄부터 T개의 테스트케이스가 차례로 주어진다. 각 테스트 케이스의 첫 번째 줄에는 정점의 수 N(1 > N >> M >> W; std::vector adj[N]; for (int i = 0; i > X >> Y >> C; adj[X - 1].push_back(P(Y - 1, C)); adj[Y - 1].push_back(P(X - 1..

알고리즘/문제 2023. 5. 23. 14:36

벨만 포드 알고리즘이란? 벨만 포드 알고리즘(Bellman-Ford Algorithm)은 다익스트라 알고리즘과 마찬가지로 시작점을 정해주면 시작점 기준으로 다른 모든 정점으로의 최단 거리를 구해주는 알고리즘이다. 이때, 벨만 포드 알고리즘의 최대 특징은 다익스트라 알고리즘과는 달리 간선의 가중치가 음수일 때도 사용할 수 있다는 것이다. 벨만 포드 알고리즘의 구조 그럼 벨만 포드 알고리즘은 무엇이 다르기에 음수의 가중치가 있어도 최단경로를 구할 수 있는 것일까? 벨만 포드 알고리즘은 2중 for문을 이용하여 가능한 모든 경우를 전부 다 체크한다. 우선 최단 경로의 정의를 알아볼 필요가 있다. 최단 경로란 같은 정점을 두 번 지날 일이 없다는 것을 의미한다. 즉, 가능한 최단 경로의 간선 개수는 많아봐야 V..

알고리즘/이론 2023. 5. 23. 14:16

문제 N개의 정점으로 이루어진 그래프 G가 있고, 그래프 G의 모든 간선은 가중치를 2개 가지고 있다. 이 말은 특정 노드 i에서 특정 노드 j로 가는 가중치가 2개 있다는 것이다. 0번 정점에서 1번 정점으로 가는 최단 경로를 찾아야 한다. 경로의 비용은 경로에 있는 간선의 가중치 1을 모두 더한 값인 W1와 가중치 2를 모두 더한 값인 W2를 곱해서 구할 수 있다. 여기서 곱하는 것에 유의하며 문제를 풀어야 한다. 입력 첫째 줄에 정점의 수 N이 주어진다. (2 b.idx) return true; else return false; } return false; } }; std::vector varr[2][21]; int dist[2][21]; int INF = 1e8; int Dijkstra(int S..

알고리즘/문제 2023. 5. 23. 11:13

문제 방향그래프와 시작점이 정해지고 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성해야 한다. 입력 첫째 줄에 정점의 개수 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