알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17270 17270번: 연예인은 힘들어첫 번째 줄에는 약속 장소 후보의 수 V와 약속 장소를 연결하는 총 길의 수 M이 주어진다. (2 ≤ V ≤ 100, 1 ≤ M ≤ 1,000) 그리고 다음 M개의 각 줄에는 a, b, c 가 주어진다. a, b는 길의 시작과 끝이www.acmicpc.net다익스트라를 이용해 풀 수 있는 문제였습니다.지헌이와 성하가 만날 때, 최적의 장소를 구하는 문제입니다. 최적의 장소는 구하는 방법은 1. 둘이 만날 때, 거리는 최소가 되어야 합니다. 2. 출발지는 장소 후보에서 제외됩니다. 3. 지헌이가 성하보다 더 일찍 도착해야 합니다. 4. 위의 조건을 모두 만족하는 장소가 있다면, 지헌이한테 가장..

문제 링크입니다. https://www.acmicpc.net/problem/23801 23801번: 두 단계 최단 경로 2첫째 줄에 정점의 수 N (10 ≤ N ≤ 100,000), 간선의 수 M (10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타www.acmicpc.net다익스트라를 사용하는 문제입니다.무조건 들려야하는 점이 존재할 때, 해당 점을 하나라도 들리면서 갈 수 있는 최소 비용 경로를 구하는 문제입니다. 들려야하는 점의 갯수가 최대 N-3개이니 100,000개 정도가 주어집니다. 따라서, X->K + K->Z를 점마다 확인하는 것은 시간 초과가 될 것입니다.(K를 들려야 하는 점으로 ..

문제 링크입니다. https://www.acmicpc.net/problem/22865 22865번: 가장 먼 곳$N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들이 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할www.acmicpc.net다익스트라를 이용하는 문제입니다.1 ~ N까지 중에서, 친구의 위치가 3개가 주어질 때, 최소 거리가 가장 긴 위치를 찾는 문제입니다. 1부터 시작해 1->1 ~ 1->N,,,,,,N->1 ~ N->N까지 모든 경우를 구한 뒤, 3지점까자의 각각의 거리를 비교해서 최솟값을 찾는 것은 다익스트라를 100,000번 돌려야 되기 때문에 시간초과가 생기게 됩니다. 따라..

문제 링크입니다. https://www.acmicpc.net/problem/20007 20007번: 떡 돌리기첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y 다익스트라를 통해 거리를 구한 뒤, *2를 하면 됩니다. 거리가 가장 짧은 곳부터 오름차순으로 방문하기 때문에 거리를 구한 뒤, 정렬을 해주면 됩니다...

문제 링크입니다. https://www.acmicpc.net/problem/23793 23793번: 두 단계 최단 경로 1서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으www.acmicpc.net다익스트라를 이용한 문제입니다.문제 시간이 0.3초이며, N과 M의 값이 큰 만큼, 시간을 생각하면서 풀어야하는 문제입니다. 먼저, 문제를 풀기 위해 방향을 생각해보겠습니다. 두개를 출력하면 됩니다. 1. X -> Y -> Z를 들려서 올 때의 최소 비용 2. X -> Z(Y를 제외)로 올 때의 최소 비용 2번은 간단합니다. 다익스트라를 실행할 때, Y점에 도달한다면, 해당 경우를..

문제 링크입니다. https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net다익스트라 알고리즘을 활용한 문제입니다.문제를 풀기 위해선 1->N 점까지 가는 최단 거리가 1->민준->N 점으로 가는 최단거리와 같은 것인지를 알아야 했습니다. ->이 두 경우의 값이 같다면 항상 민준이는 건우를 도울 수 있기 때문입니다. 따라서 1->N까지 가는 다익스트라로 원래 최단 거리를, 1->민준 + 민준->N의 최단 ..

문제 링크입니다. https://www.acmicpc.net/problem/13424 13424번: 비밀 모임입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방www.acmicpc.net다익스트라를 이용해 푸는 문제입니다. 1~N번 정점까지 친구들이 있는 곳까지 거리를 각각 구한 뒤, 이를 모두 비교하면 되는 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define INF 21000..

문제 링크입니다. https://www.acmicpc.net/problem/13398 13398번: 연속합 2첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net다이나믹 프로그래밍을 이용해 푸는 문제입니다.연속된 수를 선택해 수열의 최댓값을 구하는 문제입니다. 이때, 수열의 수 중, 하나를 빼고 더할 수 있기에 점화식을 구해야했습니다. 저는 배열을 2차원 배열로 만들었습니다. [X][2]로 만들어, [X][0]은 수를 하나도 빠짐없이 전부 더할 때, [X][1]은 수열 중, 하나를 빼고 더할 경우로 만들었습니다. [X][0]에서 구할 수 있는 i..

문제 링크입니다. https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net다익스트라를 이용하는 문제입니다.가중치가 주어졌을 때, 연결할 수 있는 최솟값을 출력하는 문제입니다. 연결했을 때의 최솟값만 출력하면 되기에 다익스트라 알고리즘을 이용해서 풀어주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #i..

문제 링크입니다. https://www.acmicpc.net/problem/1719 1719번: 택배첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경www.acmicpc.net다익스트라를 이용해 푸는 문제입니다. 거리를 출력하는 것이 아닌, 최단거리를 가기 위해서 처음으로 가는 정점을 출력하면 됩니다. 즉, 기본적인 다익스트라를 사용하면서, 거리가 바뀔 때마다 가는 정점을 같이 바꿔줘야한다는 의미입니다. 먼저 1~N까지 모두 출력해야 하기에 반복문을 통해 i번 정점을 기준으로 탐색을 시작할 수 있도록 해줍니다. 정점에서 탐색을 시작했다면 이제 갈 수 ..

문제 링크입니다. https://www.acmicpc.net/problem/1446 1446번: 지름길첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이www.acmicpc.net다익스트라를 이용한 문제입니다. 현재 위치에서 지름길을 통해 이동하거나, 다음 위치로 이동하는 과정을 거쳐, 원하는 목적지까지 최소 이동거리로 이동하는 문제입니다. 먼저 Distancs배열을 만들어줍니다. 해당 배열을 N번째 위치를 얼마의 최솟값으로 이동할 수 있는지를 저장하는 배열입니다. -> 해당 배열은 처음에 무한히 큰 값으로 초기화를 해줘야합니다. 초기화를 통해 큰 ..

문제 링크입니다. https://www.acmicpc.net/problem/18232 18232번: 텔레포트 정거장첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000)) 두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E) 그 다음 줄부터 Mwww.acmicpc.netBFS를 이용한 문제입니다.현재 위치 S에서 출발해 E로 도착하려고 할 때, 걸리는 최소 시간을 구하는 문제입니다. 이동할 수 있는 방법은 +1 or -1 or 이어진 텔레포트를 이용해 움직일 수 있습니다.(움직일 때 걸리는 시간은 모두 1입니다.) 하나의 점에서 텔레포트가 여러개가 연결될 수도 있습니다..