프로그래머스12 [kotlin, 프로그래머스] 최소신장트리 문제와 입출력최소 신장 트리 (Minimum Spanning Tree, MST)의 정의와 특징정의최소 신장 트리는 가중치가 할당된 무방향 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소가 되는 트리입니다.특징트리의 간선 수: (V - 1)개의 간선을 가집니다.사이클 없음: 트리 구조이므로 사이클을 형성하지 않습니다.가중치 최소화: 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되어야 합니다.사용 예통신 네트워크 구축: 노드들을 가장 적은 비용으로 연결할 때 사용됩니다.최소신장트리(MST) 구현 방법 - 크루스칼 알고리즘, 프림 알고리즘 사용 크루스칼간선을 가중치 순으로 정렬 후, 작은 것부터 선택 (사이클 방지)간선 정렬 + 유니온 파인드 (Union-Find)프림정점 기준으로, 현재 트리.. 2025. 4. 12. [프로그래머스 kotlin] 롤케이크 자르기 시간 초과 발생 코드 fun solution(topping: IntArray): Int { var count=0 for(i in topping.indices){ val set1 = mutableSetOf() val set2 = mutableSetOf() for(j in 0.. i){ set1.add(topping[j]) } for(k in i+1 until topping.size){ set2.add(topping[k]) } if(set1.size==set2.size){ count++ } } println(count) .. 2024. 7. 1. [프로그래머스] N개의 최소공배수 (kotlin) 문제해결 point두 수의 최대공약수 구하기 -> 유클리드 호재법 https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 1. 유클리드 호재법을 사용하여 배열에 인접한 두 수의 최대공약수를 구한 뒤, (두 수의 곱 나누기 최대공약수= 최소공배수) 법칙을 이용하여 최소공배수를 구한다. 2. 구해진 최소공배수를 answer에 반영하고 다음 3번째 인덱스와 반영된 answer의 최소공배수를 구한다. 4. 이와 같은 방법으로 마지막 인덱스의 값과도 최소공배수를 구해 answer에 반영합니다. 전체코드fun solution_l(arr: IntArray): Int { var answer .. 2024. 6. 13. [프로그래머스] 카펫 (kotlin) 문제 설명문제 해결 Point(행- 2) * (열- 2 ) = yellow의 개수이다. 주어진 brown과 yellow의 합은 전체 카펫의 넓이이다. 그러므로 문제에서 정답인 return의 값은brown과 yellow의 합의 약수를 구한 뒤, 곱했을 때 합이 되는 수의 조합을 고려하면 된다. 예를들어 brown : 10 yellow : 2 일 경우 합은 12 나올 수 있는 경우의 수는 (1, 12) , (2, 6) ,(3, 4) (4, 3) ,(6, 2), (12, 1) 이다. 일단 가로의 길이가 세로보다 길거나 같다고 제한사항에 있으므로 경우의 수가 (1, 12) , (2, 6) , (3, 4)은 제외한다. (4, 3) (6, 2) (12, 1) 이 조합중에서 , (행-2)*(열-2)=yellow .. 2024. 6. 11. 이전 1 2 3 다음
