알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/9470 9470번: Strahler 순서지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳www.acmicpc.net위상 정렬 알고리즘을 이용한 문제입니다.주어진 강의 Strahler 값을 구하는 문제입니다. Strahler 순서를 구하는 방법은 1. 강이 시작하는 곳은 순서가 항상 1이다. 2. 강이 만나는 곳은 들어오는 강 중, 가장 큰 Strahler 값을 가져온다. 2-1. 이때, 가장 큰 Strahler 값이 2개 이상이면 해당 값의 1을 더한 값이 해당 강의 Strahler 순서이다...

문제 링크입니다. https://www.acmicpc.net/problem/26372637번: 장난감 조립첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주www.acmicpc.net위상 정렬을 역방향으로 이용하는 문제입니다.기본 부품, 중간 부품, 완제품이 존재합니다. 중간 부품과 완제품을 만들기 위한 부품 번호와 갯수가 주어질 때, 완제품을 만들 경우 몇 개의 기본 부품이 사용되는지를 구하는 문제입니다. 문제에서 주어진 예시를 확인해보겠습니다.(입력에서 1,2,3,4 -> 기본 부품 / 5, 6 -> 중간 부품 / 7 -> 완제품임을 ..

문제 링크입니다. https://www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내www.acmicpc.net간단한 것 같으면서도 풀 방법이 쉽게 떠오르지 않는 문제였습니다.주어진 파란색 간선 중, 최소 스패닝 트리를 구현하기 위해서 무조건 사용해야 하는 간선이 존재할 수 있습니다. 그러한 간선이 몇 개인지를 찾기 위해서 빨간색 간선을 오름차순 기준으로 만들어 정렬을 해준 뒤, 최소 스패닝 트리를 사용해주면 됩니다. 이때, 쉽게 구현하기 위해서 파란색 간선에는 1의 가중치, 빨간색 간..

문제 링크입니다. https://www.acmicpc.net/problem/1185 1185번: 유럽여행첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비www.acmicpc.net어려운 최소 스패닝 트리 문제였습니다.먼저, 문제를 풀기 위해서는 일반적인 최소 스패닝 트리의 방식으로 그래프를 구성하면 답이 다르다는 것을 알아야합니다. 간선의 가중치를 기준으로 오름차순 정렬해서 만든 그래프는 다음과 같은데, 답보다 더 큰 값이 나오는 것을 알 수 있습니다.따라서, 간선의 가중치로 정렬을 한다면 안된다는 것을 알 수 있습니다. ..

문제 링크입니다. https://www.acmicpc.net/problem/1833 1833번: 고속철도 설계하기첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음www.acmicpc.net최소 스패닝 트리를 이용한 문제입니다.미리 연결된 도로들이 주어질 때, 남은 도로들로 모든 도시를 연결하려고 합니다. 이때의 연결된 도로 비용의 최솟값과 어떤 도로들이 추가로 연결되었는지를 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #inclu..

문제 링크입니다. https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰!교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net다익스트라와 그래프 탐색을 이용한 문제입니다.두 명의 팀장이 주어질 때, 각 팀장을 기준으로 2개의 조로 나눕니다. 이때, 모든 학생에게 공지를 전달할 떄의 최소 비용을 구하는 문제입니다. 2명의 조장에게 공지를 전달하니, 2명의 조장은 서로 연락을 통해 공지를 알릴 필요가 없습니다. 그렇다면, 2명을 연결하는 비용 중에서 가장 큰 비용을 찾고 해당 간선을 없애 2개의 조..

문제 링크입니다. https://www.acmicpc.net/problem/23743 23743번: 방탈출첫 번째 줄에는 방의 개수 $N$과 설치할 수 있는 워프의 개수 $M$이 주어진다. ($2 \le N \le 200\,000$, $1 \le M \le 100\,000$) 다음 $M$개의 줄에는 워프의 정보를 나타내는 세 정수 $a_i$, $b_i$, $c_i$가 공백으www.acmicpc.net최소 스패닝 트리를 이용한 문제입니다.워프와 비상탈출구를 설치해 모든 친구들이 탈출하려고 할 때 걸리는 최소 시간을 구하는 문제입니다. 워프는 방을 잇는 역할이며, 비상탈출구는 설치된 방에서 밖으로 탈출할 수 있도록 해줍니다. 따라서, 워프와 방을 적절히 사용해 탈출해야 합니다. 이 문제릂 푸는 방법은 간단합..

문제 링크입니다. 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을 출력해줘야 합니다. 모든 견물을 연결하는 방법은 최소 스패닝 트리를 통해 구해주면 됩니다. 문제는 전부 ..