Algorithm44 [백준] 1238. 파티 / Java https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ✔ 문제 풀이 조건 분석 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 각각의 학생들은 파티 장소 X에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 학생들은 최단 시간에 오고 가기를 원한다. 왕복시간이 가장 긴 학생의 소요시간을 구하라. 풀이 학생들은 최단시간에 이동을 원하므로 최단 거리 알고리즘 다익스트라를 생각하였다. 이때, 이동방.. 2023. 8. 17. [Algorithm] BackTracking / Java BackTracking = DFS + prunning ✔ 백트래킹이란? 백트래킹은 한마디로 가지치기(prunning)를 가미한 너비우선탐색(DFS)입니다. 다시 말해서, DFS로 해를 찾아가는 과정에서 수시로 현재 경로의 유망성을 판단하여 유망하지 않음이 판단되면 더이상 나아가지 않고 이전 노드로 돌아가 다른 경로를 탐색하는 방식입니다. 이어서 백트래킹과 완전탐색을 비교함으로써 백트래킹의 특성을 알아보겠습니다. ✔ 백트래킹과 완전탐색(DFS)의 차이 완전탐색과 구분되는 백트래킹의 핵심적인 특성은 '가지치기'에 있습니다. 완전탐색이 모든 경로를 탐색하는 데 반해 백트래킹은 불필요한 경로를 조기에 차단함으로써 탐색 소요를 줄입니다. 따라서 백트래킹의 효율성은 가지치기의 조건에 달려있다고 볼 수 있습니다. 다.. 2023. 8. 16. [Math] 부분집합과 멱집합 / Java 부분집합(Subset)과 멱집합(Power Set) 집합 A와 B가 있을 때, B의 특정 원소 x가 반드시 A의 원소이면 B를 A의 부분집합이라고 합니다. 그리고 이러한 부분집합(Subset)의 모든 경우의 수로 구성된 집합을 멱집합이라고 합니다. 부분집합을 Power Set으로 부르는 경우가 있는데 엄밀히 따지면 부분집합과 멱집합은 구분되는 개념입니다. 구현 구현 방식은 다음 두 가지가 있습니다. 재귀와 방문배열을 활용한 방식 비트마스킹을 활용한 방식 Java Code public class PowerSet { static int[] arr = {1, 2, 3}; static int n = arr.length; // 주어진 수의 갯수 static boolean[] visited = new boolean.. 2023. 8. 14. [Math] 순열(Permutation) / Java 순열(順列) 순서를 고려해 나열한 경우의 수. 즉, 서로 다른 n개 중 r개를 골라 순서를 정해 나열하는 경우의 수(nPr)를 의미합니다. 예를 들어, 다섯 명의 학생 중 반장 1명과 부반장 1명을 뽑는 경우의 수를 구하는 것이 순열에 해당한다고 볼 수 있습니다. 공식은 다음과 같습니다. 구현 주어진 수의 배열이 1, 2, 3일 때 두 개를 뽑는 순열의 경우의 수를 출력하는 코드입니다. 구현 방식은 두 가지입니다. 재귀와 방문배열을 활용한 방식 비트마스킹을 활용한 방식 // 순열(nPr) - n개의 값 중 r개를 순서대로 뽑는 경우의 수 public class Permutation { static int[] arr = {1, 2, 3}; static int n = arr.length; // 주어진 수의 .. 2023. 8. 13. 이전 1 2 3 4 5 ··· 11 다음
