계란 블로그

피보나치(Fibonacci) 수열이란? 1, 1, 2, 3, 5, 8, .. 와 같이 f(x) = f(x - 2) + f(x - 1); 을 만족하는 수열을 말한다. (첫 항: f(0) = 0 또는 f(1) = 1) 아주 큰 자연수 n에 대하여 피보나치 수열의 n 번째 값은 어떻게 구할 수 있을까? 첫 번째 시도 [Long] static 으로 선언한 List 안에 하나씩 값을 넣어준다. list = [1, 1, 2,3, 5, ...] 해당 리스트에 메모이제이션을 적용했다. static List list = new ArrayList(); private static void fiboFunc(int idx) { if (idx == 1 || idx == 2) { list.add(idx, 1L); return; }..

1. 수들의 합 4 - 골드 4 출처 - https://www.acmicpc.net/problem/2015 Sol) 스터디원 코드 JW - 440 ms public class Test3 { public static BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); public static BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out)); public static int N; public static int K; public static Map nums = new HashMap(); public static long result; pub..

1. 단절점과 단절선 - 실버 1 출처 - https://www.acmicpc.net/problem/14675 MySol) 트리 1380ms public class Test1 { static ArrayList[] lists; // 리스트로 이뤄진 배열 public static void solution(int t, int k) { if (t == 2) { System.out.println("yes"); return; } if (lists[k].size() >= 2) { // k번 노드와 연결된 노드의 개수 System.out.println("yes"); return; } System.out.println("no"); } public static void main(String[] args) throws IO..

1. 호석이 두 마리 치킨 - 골드 5 출처 - https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net Sol) 스터디원 jm - 플로이드 워셜 public class Main { static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); static int N; static int M; static int[][] ..

1. k진수에서 소수의 개수 구하기 09-04 일 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ================================= 86점 ================================= 소수인지 확인하는 메서드를 만든다. k진수로 바꾸는 while문 => 다음부터는 k진법으로 바꿀 때, Integer.toString(n, k)를 쓰도록 하자! 0이 나올 때마다 pre0Idx를 업데이트해준다. 어..

1. 팔 - 실버1 08-28 일 출처 https://www.acmicpc.net/problem/1105 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net MySol) ======= 미해결 코드 ======== import java.util.Scanner; public class Test { static int findEight(String s){ int eightCnt = 0; for(char c : s.toCharArray()) { if (c == '8') { ++eightCnt; } } return eightCnt; } public s..

1. 색종이 붙이기 - 백트래킹 출처 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net Sol) 476ms // 색종이 붙이기 import java.util.Arrays; import java.util.Scanner; public class Practice1 { static int [] paper = {0, 5, 5, 5, 5, 5};// 사이즈 1 ~ 5까지 붙일 수 있는 색종이 static int min = Integer.MAX_VA..

1. 카카오 프렌즈 컬러링북 - lv 2 출처 https://school.programmers.co.kr/learn/courses/30/lessons/1829 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr MySol) 9.1ms - 전형적인 DFS알고리즘 문제이다. import java.util.Arrays; // 프로그래머스 컬러링북 - DFS public class Test1 { static int[][] Direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; static boolean[][] Visited; static..

1. 파티 - 골드 3 출처 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 Sol) 스터디원 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue..

1. 등굣길 - lv 3 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Sol) // 프로그래머스 - 등굣길 import java.util.Arrays; public class Practice2 { public static int solution(int m, int n, int[][] puddles) { int mod = 1000000007; int[][] board = new int[n + 1][m + 1]; for(int i = 0;..