728x90 Algorithm77 [Algorithm] Kruskal Kruskal MST를 만드는 알고리즘 입니다. 적은 비용으로 노드를 연결하는 것이 핵심입니다. Kruskal 알고리즘을 구현하기전 MST 를 알아야 합니다. 맨아래 링크를 참조해주시면 됩니다. 알고리즘 순서 에지들을 오름 차순으로 정렬한다. 에지들을 그 순서대로 하나씩 택한다. 싸이클 검사를 한다. 선택된 에지의 수가 n-1 개의 에지가 선택되면 종료한다. 눈으로 한번 보면 편합니다. 싸이클을 검사하는 방법 위에서 싸이클이 생겼을때 우리는 선택된 엣지를 추가 하지 않고 그냥 넘어 갔습니다. 집합을 사용하여 어떻게 싸이클을 검사하는지 파악해 보겠습니다. 처음 모든 노드들을 집합으로 만듭니다. {A} {B} {C} {D} {E} {F} {G} {H} {I} 집합에 선택된 노드를 넣어 준다. 선택한 간선을 .. 2021. 8. 11. [프로그래머스] 피보나치 문제 분석 피보나치를 구현해서 풀면된다. 하지만 문제 중 2이상의 n 이 입력이 되었을때 N 번째 피보나치 수를 1234567 로 나눈 나머지 리턴... 조건이 불친절하고 명확하지가 않다. 그래서 여러가지 시도를 해봤다 1. 구한 피보나치 마다 %1234567 을 하란것인가? 2. 전체를 구한 값에서 %1234567 을 하란말인가? 1번이 맞았다. 뭔가 효율성 검사도 할지 몰라서 DP 를 이용해서 풀었다. 피보나치는 반복된 값이 나오기 때문이다. 구현 class Solution { private long []dp; public long fibo(int n) { if(dp[n] != 0) { return dp[n]; } dp[n] = (fibo(n-1) + fibo(n-2)); return dp[n] % .. 2021. 8. 10. [프로그래머스] JadenCase 문자열 만들기 문제 분석 레벨2 문제인데 레벨1 보다 쉬운것 같다. 주어진 string을 모두 소문자로 변환한다. 첫번째 문자를 대문자로 바꾼다. 앞의 문자가 공백이었다면 다음문자를 대문자로 변환한다. String 보다 StringBuilder 써서 쉽게 교체해 주었다. 구현 import java.util.*; class Solution { public String solution(String s) { String answer = ""; s = s.toLowerCase(); Character.toUpperCase(s.charAt(0)); StringBuilder tmpString = new StringBuilder(s); for(int i=0; i < s.length(); i++) { char tmp = ' '; if.. 2021. 8. 10. [Algorithm] MST(Minimum Spanning Tree) MST 란? Minimum Spanning Tree 최소 신장 트리이다. 간선의 가중치를 고려 하여 최소 Spanning Tree 를 만든다. 싸이클이 없는 연결된 무방향 그래프를 트리 라고 한다. 모든 정점들이 연결이 되어 있어야 된다. 가중치의 합이 최소가 되어야 한다. 해가 유일하진 않다. - 최소 비용을 찾는 트리이기 때문에 동일한 가중치의 간선이 있을경우 해가 여러개가 될수 있다. Kruskal 알고리즘, Prim 알고리즘 이 있다. MST를 들어가기전에 Spanning Tree 를 알고가야한다. Spanning Tree 신장트리라고 한다. 그래프의 모든 정점을 가지는 트리이다. 특징 트리의 특징은 모두 포함된다. 하나의 그래프는 여러 Spanning Tree 를 가질 수 있다. 그림설명 MST.. 2021. 8. 10. 이전 1 ··· 6 7 8 9 10 11 12 ··· 20 다음 728x90 반응형
