알고리즘 모음(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/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리가 주어졌을 때, 쿼리를 기준으로 자신을 포함한 자식노드의 개수를 구하는 문제입니다. 루트노드는 주어졌기 때문에 루트노드부터 시작해 자식의 개수를 찾으면 됩니다. 간선을 저장할 때, 양뱡향으로 저장하기에 부모와 자식 노드의 구분은 이전에 방문을 했는지 여부를 저장하는 check 배열을 통해 했습니다. 자식노드일 경..

문제 링크입니다. https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 플로이드 와샬 혹은 DFS를 이용해 풀 수 있던 문제입니다. 플로이드 와샬로 푸는 문제였지만, DFS를 이용하면 더 쉽게 풀 수 있었습니다. 1~N번까지 무게의 비교가 주어질 때, X번 물건과 비교할 수 없는 물건이 몇개인지를 구하는 문제였습니다. 그렇다면, 전부 비교할 수 없다면 값은 N-1이 될 것입니다. 여기서, 자신보다 큰 물건과 작은 물건의 갯수..

문제 링크입니다. https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net DFS 혹은 플로이드 워셜을 이용해서 풀 수 있는 문제입니다. 저는 DFS를 이용해 풀었습니다. 자신의 키 순서를 정확히 알기 위해서는 자기보다 작은 학생의 수와 큰 학생의 수의 합이 N-1의 값이 되면 됩니다. 예제 입력에서 4의 경우에는 자기보다 작은 학생은 3명, 큰 학생은 2명이기에 자신이 3번째로 크다는 것을 알 수 있다는 것입니다. 따라서 DFS를 통해 자신보다 작은 학..

문제 링크입니다. https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net DFS를 이용한 문제입니다. 첫번째 열이 다른 빵집, 마지막 열이 자신의 열일 때, 파이프라인을 최대 몇개까지 이을 수 있는지 구하는 문제입니다. 파이프 라인을 이을 수 있는 방법은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선인 총 3개입니다. 파이프라인을 최대로 짓는 수를 구하는 문제이기에, 첫째 열에서 모든 행의 값을 전부 DFS로 확인해봐야합니다. X번째 행에서 시작한 파이프가 마지막 ..

문제 링크입니다. https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 중위 순회를 이용해 푸는 문제였습니다. 1부터 N까지 열이 존재할 때, 트리의 노드를 적정하게 배치하여 하나씩만 위치하게 합니다. 이때, 최대 길이를 가지는 행을 구해주면 되는 문제입니다. 이 문제를 트리를 탐색하는 3가지 방법 중에, 중위 순회 방법이 가장 적당합니다. 왜냐하면, 중위 순회는 왼쪽 자식 -> 부모 -> 오른쪽 자식의 순서로 탐색을 진행하는데 1..

문제 링크입니다. https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net DFS를 이용해 푸는 문제입니다. 윗 줄의 숫자를 하나씩 선택할 때마다, 밑에 붙어 있는 숫자도 같이 선택됩니다. 윗 줄의 숫자를 선택해, 밑의 줄의 숫자와 같게 뽑으려고 할 때 몇 개, 어떤 숫자를 뽑아야하는지 구하는 문제입니다. 이 문제를 푸는 핵심은 윗 줄과 아랫 줄의 숫자를 연결해주는 겁니다. 만약 윗 줄이 1, 아랫 줄이 3이라면, connect[1] = 3..

문제 링크입니다. https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS를 이용해 푸는 문제입니다. 사이클이 이루어져 있을 때, 이를 어떻게 찾는지 물어보는 문제입니다. 문제를 해석했을 때, 가장 쉬운 접근은 "X번부터 사이클이 존재한다면, 도착점도 X번이니 DFS를 통해서 X가 X에 도착할 수 있는지를 확인하면 된다." 입니다. 하지만, N의 값이 100,000 이하이기에 모든 점들을 DFS탐색 하기에는 시간이 부족합니다. 따라서 사이클을 확인하는..

문제 링크입니다. https://www.acmicpc.net/problem/24484 24484번: 알고리즘 수업 - 깊이 우선 탐색 6 정점 1번에서 정점 4번을 방문한다. 정점 4번에서 정점 3번을 방문한다. 정점 3번에서 정점 2번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 4, 3, 2, 0이다 www.acmicpc.net 해당 문제에서 내림차순을 해주면 되는 문제입니다. 자세한 설명은 해당 글을 참고해주세요. https://junseok.tistory.com/298 백준 24483 - 알고리즘 수업 - 깊이 우선 탐색 5(C++) 문제 링크입니다. https://www.acmicpc.net/problem/24483 24483번: 알고리즘 수업..

문제 링크입니다. https://www.acmicpc.net/problem/24483 24483번: 알고리즘 수업 - 깊이 우선 탐색 5 정점 1번에서 정점 2번을 방문한다. 정점 2번에서 정점 3번을 방문한다. 정점 3번에서 정점 4번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 2, 3, 4, 0이다 www.acmicpc.net DFS를 이용한 문제입니다. 노드의 방문 순서 및 노드 깊이를 구하는 문제였습니다. 방문 순서는 변수 하나를 통해 저장해주면 됩니다. 저는 Count 변수를 하나 만들어, 노드를 방문할 때마다 1씩 증가해 넣어줬습니다. 노드 깊이는 방문 순서와 다르게 다른 노드를 방문했다고 1씩 증가하는게 아닙니다. 이전 노드의 깊이에서 1..

문제 링크입니다. https://www.acmicpc.net/problem/24482 24482번: 알고리즘 수업 - 깊이 우선 탐색 4 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 4번 노드이다. 4번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 2번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net DFS를 이용해 방문 노드의 깊이를 구하는 문제입니다. 방문 노드의 순서가 아닌, 깊이를 방문하는 것이기에, 노드를 방문할 때마다, 1를 증가해 값을 입력하면 안됩니다. 또한, 인접 노드는 내림차순으로 방문하기에, 정렬 기준을 세우거나, reverse를 사용해 탐색을 해야했습니다. 자세한 것은 코드를 참고해주세요. #define..