PS(Problem Solving)/BOJ244

• [백준/BOJ] 6497번: 전력난 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 해설 문제를 보면 MST 알고리즘을 사용해야 한다는 것을 알아야 한다. 최소 신장 트리를 구해 총 비용에서 최소 비용을 빼어 절약할 수 있는 최대 액수를 구한다. 어떠한 정점에서 시작해야 된다와 같은 조건이 없으므로, 크루스칼 알고리즘을 사용하였다. 이 문제에서 주의할 점은 입력에 있다. 처음 제출했을 때, 런타임 에러가 나 무엇이 문제인지 고민하다 질문 검색에 들어가 나랑 같은 케이스인 사람들이 있는.. PS(Problem Solving)/BOJ 2022. 7. 28.

• [백준/BOJ] 14950번: 정복자 문제 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 해설 모든 도시를 정복하는데 드는 최소 비용을 구하는 문제이다. 이 문장을 보고 MST 알고리즘을 떠올려야 한다. MST를 떠올렸다면, 이를 크루스칼 알고리즘과 프림 알고리즘 중 어떤 알고리즘으로 해결할지 정해야 한다. 이 문제는 1번 도시부터 시작해서 이와 연결된 도시를 정복해나가야 한다. 따라서 프림 알고리즘이 더 적절하다 생각했다. 문제를 보면 "한 번 도시가 정복되면, 모든 도시는 경계를.. PS(Problem Solving)/BOJ 2022. 7. 28.

• [백준/BOJ] 21924번: 도시 건설 문제 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 해설 최소 신장 트리(MST)에 대해 알고 있다면, 굉장히 쉬운 문제이다. 모든 간선의 비용을 합한 값에서 최소 신장 트리를 구해 그만큼의 비용을 빼주면 된다. 나는 크루스칼 알고리즘을 이용하였다. 주의할 점으로는 입력 범위가 크므로 int형을 사용한다면 틀리게 된다. .. PS(Problem Solving)/BOJ 2022. 7. 27.

• [백준/BOJ] 4386번: 별자리 만들기 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 해설 처음 입력으로 별의 개수와 별의 좌표를 입력받는다. 이번 문제에서는 기본적인 수학의 개념도 필요하다. 두 점 사이의 거리를 구해야하기 때문이다. 두 점 사이의 거리를 구하는 공식은 다음과 같다. √(x2-x1)2 + (y2-y1)2 두 별 사이의 거리를 구하는 방법을 알았다면, 별 거 없다는 것을 다들 알 수 있다. 이제 크루스칼 알고리즘을 이용하여 최소 비용을 구하면 된다. 이 때 소수.. PS(Problem Solving)/BOJ 2022. 7. 27.

• [백준/BOJ] 1647번: 도시 분할 계획 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 해설 1. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 2. 마을에는 집이 하나 이상 있어야 한다. 3. 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 4. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 위는 문제에서 .. PS(Problem Solving)/BOJ 2022. 7. 27.

• [백준/BOJ] 13418번: 학교 탐방하기 문제 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 해설 MST는 최소 신장 트리이다. 즉, 가중치가 가장 낮은 트리를 구하는 것이다. 이는 크루스칼 알고리즘과 프림 알고리즘으로 구할 수 있다. 그렇다면 반대로 신장 트리 중 최악의 경우도, 크루스칼 알고리즘과 프림 알고리즘으로 구할 수 있다는 얘기가 된다. 이 문제에서는 (최악일 경우의 피로도 - 최소일 경우의 피로도)를 구해야 한다. 나는 입구에서 시작을.. PS(Problem Solving)/BOJ 2022. 7. 26.

• [백준/BOJ] 14621번: 나만 안되는 연애 문제 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 해설 연결그래프에서 최소 신장 트리를 찾는 문제이다. 고려할 점은 다음과 같다. 연결된 두 노드가 남초, 여초 학교여야 한다. 두 노드가 모두 남초거나, 여초라면 연결되지 않는다. 만약 두 노드가 같다면, 우선순위 큐에 넣을 필요가 없다. 두 노드간 한 개의 간선만 있는 것이 아니라 여러 개의 간선이 있을 수 있고, 이들 간 거리는 다를 수 있다. 이.. PS(Problem Solving)/BOJ 2022. 7. 25.

• [백준/BOJ] 16398번: 행성 연결 문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 해설 최소 신장 트리를 이용하여 푸는 문제이다. 특정 노드부터 시작하라는 말이 없기에 크루스칼 알고리즘을 사용하였다. (꼭 저 말이 있어야만 프림 알고리즘을 사용할 수 있는 것은 아니지만, 크루스칼 알고리즘의 성능이 더 좋다.) 보통의 크루스칼 알고리즘 문제들은 연결되는 두 노드와 간선의 비용을 입력하도록 한다. 하지만 이 문제에서는 모든 행성이 연결되어 있고, 각각의 행성마다 비용을 입력하.. PS(Problem Solving)/BOJ 2022. 7. 24.

• [백준/BOJ] 11725번: 트리의 부모 찾기 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 DFS를 이용하여 해결할 수 있는 문제이다. 트리 상에 연결되는 두 정점이 부모-노드 구분이 없기 때문에 양방향으로 넣어줘야한다. 또한 문제에서 트리의 루트를 1이라고 정했기 때문에, 1은 먼저 방문처리 해준 후, DFS를 실행시킨다. 소스 코드 private lateinit var arr: Array private lateinit var parent: IntArray private lateinit var visited: BooleanArray fu.. PS(Problem Solving)/BOJ 2022. 7. 23.

• [백준/BOJ] 1197번: 최소 스패닝 트리 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 해설 최소 신장 트리의 기본적인 문제이다. 크루스칼 알고리즘과 프림 알고리즘으로 해결이 가능한데, 나는 우선 크루스칼 알 고리즘을 이용하여 해결하였다. 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택해 나가는 알고리즘이다. 자세한 설명은 아래를 참고하면 된다. https://jjunsu.tistory.com/221 [알고리즘] 크루스칼 알고.. PS(Problem Solving)/BOJ 2022. 7. 22.

• [백준/BOJ] 1922번: 네트워크 연결 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 해설 최소 비용을 구하는 문제로 최소 신장 트리를 이용하면 된다. 최소 신장 트리를 구현하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있는데, 나는 이 중 크루스칼 알고리즘을 이용하여 문제를 해결하였다. 크루스칼 알고리즘에 대해서는 밑의 글을 확인해보는 것을 추천한다. https://jjunsu.tistory.com/221 [알고리즘] 크루스칼 알고리즘(Kruscal Algorithm) 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 그리디 알고리즘(G.. PS(Problem Solving)/BOJ 2022. 7. 22.

• [백준/BOJ] 12931번: 두 배 더하기 문제 https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 해설 배열 A를 B로 만들 수도 있겠지만, 좀 더 쉽게 생각해보면 배열 B를 모두 0의 값을 가지게 만들어도 된다. 문제를 보면, 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 이를 반대로 생각하면 다음과 같다. 배열에 있는 값 하나를 1 감소시킨다. 배열에 있는 모든 값을 2로 나눈다. 여기서, 2번을 실행시키기 위해서는 모든 값이 짝수여야한.. PS(Problem Solving)/BOJ 2022. 7. 20.