MST

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 크루스칼 (유니온파인드) 1. 유니온 파인드 배열을 초기화한다. 2. 그래프 데이터를 가중치 기준으로 오름차순 정렬한다. // == Arrays.sort(costs, (o1,o2) -> Integer.compare(o1[2], o2[2])); Arrays.sort(costs, new Comparator() { @Override public int compare(int[] o1, int[] o2) { // 값이 작은 순 정렬 return o1[2] - o2[2]; } }); 3. 가중..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 import java.util.*; import java.io.*; public class Main { static in..

📍 정의 및 특징 브루트포스에서 가지치기 진행 - DFS의 한 종류 (재귀) - N이 최대 10으로 작을 경우, 백트래킹 가능 #가지치기 #DFS #재귀 📍 시간 복잡도 ▷ 중복 가능한 경우 ⋄ N^N ⋄ N = 8 까지 가능 ▷ 중복 불가한 경우 ⋄ N ! ⋄ N = 10 까지 가능 📍 필요 변수 ✔ 방문 여부 확인 배열 : boolean[] - 중복 확인용 ✔ 선택값 입력 배열 : int[] 📍 실행 과정 종료 조건 재귀 위한 for문 - 순열 : for문, 0부터 시작 / 조합 : for문, startIdx부터 시작 1) 결과값 추가 2) 재귀 ; 함수 호출할 때마다 매개변수 값 갱신하는 식으로 동작 public static void recur(int startIdx, int depth) { // ..

📍 정의 및 특징 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리 - 사이클 X - 에지 중심! - 노드가 N개일 때, MST를 구성하는 에지 개수는 항상 N-1개 - 대표 : 크루스칼(그리디), 프림 알고리즘 #사이클X #에지 #가중치합 #크루스칼 #프림 📍 필요 변수 1. 에지 클래스 - 노드 변수 2개 - 가중치 변수 2. 그래프 에지 리스트 - PriorityQueue edges 3. 유니온 파인드 배열 - int[] parent - 사이클 판단 4. 에지 개수 - int useEdge 5. 최소 가중치 합 결과 - int result 📍 실행 과정 그래프 에지 리스트, 유니온 파인드 배열 초기화 그래프 데이터를 가중치 기준으로 정렬 (참고) 가중치가 낮은 에지부터 연결 ..

🔺 문제 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 import jav..

🔺 문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83..

🔺 문제 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 import java.ut..