728x90 전체 글380 [프로그래머스] 피보나치 문제 분석 피보나치를 구현해서 풀면된다. 하지만 문제 중 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. 처음에 어떻게 풀어야 할까 하다가 몇번 실패 후 다시 풀어 봤다. 2. 스택문제여서 스택을 이용하자 3. () 는 컷을 하는 기준이 이기 때문에 () = C 로 치환했다. 4. "(" 일 경우 stack push를 해주었다. 5. C 일경우 stack 의 사이즈를 더해준다. - 이유는 ( ( C 일경우는 막대가 2개 들어 왔다 C 로 막대를 자르면 자른 지점 까지 기준으로 2개가 된다. 6 ")" 닫힌 부분이 나오면 +1 을 해준다. 막대의 끝이기 때문에 다음과 같은 공식이 나온다 - 잘라진 부분 + 나머지 부분 구현 import java.util.*; public class Main { public static void main (String[] args) { Scanner input .. 2021. 8. 10. 이전 1 ··· 63 64 65 66 67 68 69 ··· 95 다음 728x90 반응형
