알고리즘/알고리즘문풀

BOJ - 정육면체 9029번 (JAVA)

❓ 문제 - 백준 정육면체 9029번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/9029) 9029번: 정육면체 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20) 가 주어진다. 각 테스트 케이스에 대해 원목의 크기를 나타내는 W,L,H (1 ≤ W, L, H ≤ 200) www.acmicpc.net 📝 문제해결법 1. 문제 원목의 가로, 세로, 높이의 길이가 W, L, H일 때 원목을 가로, 세로, 높이 방향으로 자르는 작업을 정육면체가 될 때까지 반복적으로 자르는데 걸리는 최소 횟수를 출력한다. 2. 해결 방법 우선 DP를 통해 문제를 해결해야 한다. 소스코드에서 box 3차원 배열..

BOJ - 친구 네트워크 4195번 (JAVA)

❓ 문제 - 백준 친구 네트워크 4195번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/4195) 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 📝 문제해결법 1. 문제 친구 관계가 주어질 때 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 문제이다. 2. 해결 방법 우선, 두 친구 관계가 주어질 때 두 친구가 자신이 친구 네트워크를 통해 한 네트워크에 속하는지 아니면 다른 네트워크인지 분류해야 하므로 union find 사용하면 된다. 따라서 원래 같은 ..

BOJ - 소풍 2026번 (JAVA)

❓ 문제 - 백준 소풍 2026번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/2026) 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 📝 문제해결법 1. 문제 N명중에 K명을 소풍을 보내려고 선택해야한다. 하지만 K명 모두 친구관계이어야 하며, 만약 K명 이상인 친구관계가 존재하지 않으면 -1을 여러 개라면 번호가 작은 순서대로 K개까지만 출력해야 한다. 2. 해결 방법 우선 인접행렬로 서로의 친구관계를 표시하고, 백트래킹을 통해 조건에 맞는 경우를 구해서 k명을 선발할 ..

BOJ - 악덕 영주 혜유 20010번 (JAVA)

❓ 문제 - 백준 악덕 영주 혜유 20010번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/20010) 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 📝 문제해결법 1. 문제 해석 모든 마을과 마을을 최소한의 비용을 연결하는 비용과, 마을과 마을을 이동하는 가장 최악의 비용을 구하여라 2. 해결 방법 MST+DFS로 구하였다. 우선 MST에서 union_find을 활용하여 마을과 마을을 최소한의 비용으로 연결하는 크루스칼 알고리즘을 적용한다. 그리고 마을과 마을이 최소..