알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13905 13905번: 세부첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄www.acmicpc.net최소 스패닝 트리와 DFS를 이용해 풀었습니다.숭이의 출발위치에서 혜빈이의 위치까지 이동할 때, 숭이가 들고 갈 수 있는 최대 금빼빼로의 개수를 구하는 문제입니다. 들고 갈 수 있는 금빼빼로는 다리를 이동할 때, 해당 다리의 비용만큼만 들고 갈 수 있습니다. 따라서, 집들을 연결할 때, 비용이 작은 것들이 아닌 큰 비용을 가진 다리들로 연결해야..

문제 링크입니다. https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net다익스트라와 DFS를 이용한 문제입니다.주어진 교역로를 통해 마을들끼리 서로 연결될 수 있는 최소 비용을 구하고, 해당 연결에서 가장 큰 경로의 비용을 구하는 문제입니다. 최소 비용으로 모든 마을이 연결될 수 있게 만드는 것은 최소 스패닝 트리를 통해 쉽게 구할 수 있습니다. 문제는 가장 큰 경로의 비용을 구하는 것인데, 간단하게 최소 스패닝 트리를 구하는 과정에서 가장 작은 비용..

문제 링크입니다. https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선www.acmicpc.net최소 스패닝 트리를 이용한 문제입니다.N*N의 입력으로 정점끼리 연결된 정보가 주어질 때, 기부할 수 있는 최대 전선의 길이를 구하는 문제입니다. 최대 전선의 길이를 구하기 위해선, 컴퓨터들끼리 연결시킨 전선의 최소 길이를 구한 뒤, 전체 전선의 길이에서 빼주면 됩니다. 문제에서 모든 컴퓨터가 연결되어 있어야하며, 다른 컴퓨터들을 통해 연결될 수 있다면 서로 통신할 수 있다는 것..

문제 링크입니다. https://www.acmicpc.net/problem/1368 1368번: 물대기첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어www.acmicpc.net최소 스패닝 트리를 이용하는 문제였습니다.N개의 논에 물을 대려고 할 때의 최소 비용을 구하는 문제입니다. 논에 물을 대는 방법은 2가지가 있습니다. 1. 논에 우물을 파는 방법 2. 물이 있는 다른 논에서 자기 논으로 대는 방법 다른 최소 스패닝 트리 문제와 달리 다른 정점과의 간선 뿐만 아니라, 자기 자신의 값이 추가되었습니다. 하지만, 생각을 다르게..

문제 링크입니다. https://www.acmicpc.net/problem/21924 21924번: 도시 건설첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net최소 스패닝 트리를 이용한 문제입니다.모든 건물이 도로를 통해 연결되도록 할 때의 최솟값을 구하는 문제입니다. 다만, 모든 건물이 연결될 수가 없다면 -1을 출력해줘야 합니다. 모든 견물을 연결하는 방법은 최소 스패닝 트리를 통해 구해주면 됩니다. 문제는 전부 ..

문제 링크입니다. https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다맨위 첫 번째 줄에 T(1 n_cost){ parent[xx] = x; //자신과 연결된 부모 저장 Distance[xx] = n_cost; q.push({-Distance[xx], xx}); } } } } void solve(int num){ reset_array(); Dijstra(); if(Distance[M-1] != INF){ vector way; way.clear(); for(int i = M-1; i != 0; i = parent[i]){ // 저장된 부모들을 찾는다. way.push_back(i); } way.push_back(0); cout cost..

문제 링크입니다. https://www.acmicpc.net/problem/16118 16118번: 달빛 여우첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ bwww.acmicpc.net다익스트라를 사용하는 문제였습니다.달빛 여우와 늑대가 어느 정점을 갈 때의 최소 비용이 여우가 더 적은 정점의 개수를 찾는 문제입니다. 주의할 점은 여우는 주어진 비용으로만 가지만, 늑대는 (비용/2) -> (비용*2) -> (비용/2) ..... 의 방법으로 가게 됩니다. 그렇다면 다른 정점까지의 여우의 최솟값, 늑대의 최솟값..

문제 링크입니다. https://www.acmicpc.net/problem/2645 2645번: 회로배치회로를 n×n의 격자 판에 배치하려고 한다. 여기서 각 격자(정사각형 칸)는 범위 밖에 있는 격자를 제외하고 상, 하, 좌, 우 4개의 이웃 격자를 갖는다. 회로는 시작과 끝이 있는 연속된 이웃 격자www.acmicpc.net복잡했던 다익스트라 문제였습니다.A와 B를 최소 비용으로 이을려고 할 때의 비용을 구하는 문제입니다. 격자판 위에 다른 회로가 있을 수도 있습니다. A와 B를 이을 때, 선이 다른 회로의 위에 있을 경우, K의 비용이 들어가고, 다른 회로가 없을 경우에는 1의 비용이 들어갑니다. 따라서, 처음으로는 다른 회로가 어떻게 있는지를 구하는 것이 중요합니다. 입력에서 (3, 3, 9, 3..

문제 링크입니다. https://www.acmicpc.net/problem/13308 13308번: 주유소표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도www.acmicpc.net다익스트라와 다이나믹 프로그래밍이 사용된 문제였습니다. 이 문제는 1번부터 N번점까지 이동할 때, 필요한 최소 비용을 구하는 문제입니다. 이전에 지났던 점을 다시 지날 수 있으며, 기름을 싼 곳에서 전부 채워온 후 한번에 이동할 수 있기에 어느 정점에서, 어떤 기름값으로 채웠을 때 드는 최소 비용을 저장해줘야 했습니다. 따라서, 값을 저장해주는 배열을 ‘위치+..

문제 링크입니다. https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net다익스트라를 사용하는 문제입니다. 정해진 지점에서 시작을 하지 않는다는 것이 특징이였습니다.면접 장소가 주어졌을 때, 면접 장소에서 가장 멀리 떨어진 곳을 찾는 문제입니다. 주어진 어느 지점에서 출발하는 것이 아니기 때문에 어디서 시작해야 할지를 찾아야합니다. 만약에 N개의 지점에서 모두 확인해본다면 100,000개의 지점에서 ..

문제 링크입니다. https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있www.acmicpc.net다익스트라를 이용한 문제입니다. 비교할 값이 2개가 있기에 조심해야 되는 문제였습니다.시작 지점에서 출발해 도착 지점까지 갈 때, 쓰레기 위를 지나는 값, 근처를 지나는 값의 최소를 출력하는 문제입니다. 쓰레기의 위치는 g로 주어지며, 근처는 상하좌우인 4방향입니다. 따라서, 쓰레기의 위치를 받을 때, 근처의 위치도 같이 표시해주면 됩니다. 먼저 함수 탐색..

문제 링크입니다. https://www.acmicpc.net/problem/1486 1486번: 등산첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000www.acmicpc.net다익스트라를 2번 이용해 푸는 문제입니다. 높이를 의미하는 알파벳이 주어지고 N*M이 주어질 때, 세준이가 오를 수 있는 가장 높은 높이를 구하는 문제입니다. 세준이는 (1, 1)에서 시작하고, 높이의 차는 ‘T’이하만 이동할 수 있습니다. 다른 위치로 이동할 때 드는 시간은 1. 현재 위치보다 낮은 곳을 이동할 경우 -> 1 2. 현재 위치보다 높은 곳을 이동 -> ..