문제 처음코드 : Hash의 contains 함수가 가장 효율이 좋기에 HashMap의 contains 함수를 이용했고, all 에 대한 HashMap 을 따로 만들어 all 연산 시마다 now에 all 의 값을 할당해 주었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { HashMap now = new HashMap(); Buffered..

처음 짯던 코드는 다음과 같다 만들수 있는 최대 랜선의 길이를 max라 하면 모든 랜선의 길이를 더한 다음 k로 나눈 것이 max의 최댓값이라 생각했고 거기서 n보다 크거나 같을 때까지 1씩 빼가며 max의 값을 구해주는 것이다. public class Baek_1654 { public static void main(String[] args) throws IOException { //K개의 랜선을 모두 N개 이상의 같은 길이의 랜선으로 만들기 //만들 수 있는 최대 랜선의 길이를 구해라 //가지고 있는 랜선 갯수 1

간단해 보이지만 이 문제는 ArrayList의 contains() 메서드로 풀면 시간 초과가 난다. HashSet이나 Map을 이용해서 풀면 풀린다. 왜일까? 자료구조 시간복잡도 메서드 구현 방식 HashSet의 contains() O(1) Hashmap을 기반으로 구현 ArrayList의 contains() O(n) indexOf()를 사용해서 contain여부를 결정 HashSet은 HashMap 기반으로 구현되어 있어서 contains 메서드를 실행할때 HashMap.contains() 메서드를 불러온다. 그러므로 시간복잡도는 O(1) 이다. AllayList의 indexOf는 배열에 있는 항목의 수에 따라 시간복잡도가 결정되므로 O(n)이다. ⭐따라서 ArrayList를 사용해서 시간초과가 나거나..

처음엔 dfs를 이용해 풀어보려고 했으나 실패했다. bfs를 이용해 익은 토마토가 들어있는(1) 좌표를 q에 넣어주고, 상하좌우에 있는 토마토 중 안익은(0) 토마토가 들어있는 좌표가 있으면 익은 토마토 일수에서 1을 더해준다 즉 depth가 1 깊어질 때마다 1을 추가해 주는 것이다. 이렇게 하면 일수를 계산 가능하다. 그 후 countDay메서드를 통해 가장 깊은 depth를 cnt에 담아주고 depth는 1에서 시작했는데 일수는 0에서부터 시작했으니 날짜를 계산할 때는 1을 빼준다. 최종적으로 checkTomato메서드를 통해 안익은 토마토가 있으면 -1을 출력하고 그렇지 않으면 모든 토마토가 있은것이므로 cnt를 출력한다. import java.io.BufferedReader; import jav..

문제 풀 때마다 까먹어서 이항계수를 정리해보려 한다. 이항계수 nCr 은 n개중 r개를 선택하는 경우의 수를 의미하며 n!/r!(n-r!)로 나타낼 수 있다 알고리즘에서 이항계수를 구할 때 팩토리얼로 일일히 이항계수를 구하면 int범위를 벗어나 오버플로우가 발생하는 경우가 많다. 따라서 BigInteger를 이용해줄 수 있지만 보통은 재귀를 이용한다. 재귀를 이용할 때에도 시간초과가 날 수 있기 때문에 dp로 풀어주는 것이 일반적이다. 이항계수에는 중요한 규칙 두 가지가 있다. 1.nCr = n-1Cr + n-1Cr-1 2.nC0 = nCn = 1 이를 증명해보자 {a1,a2,a3....an}의 부분집합 중 원소의 개수가 r인 것의 개수는 nCr이다 여기서 원소의 개수가 r인 경우는 두가지로 나뉠 수 있..

문제 입출력 예시 처음 풀이 처음에는 정말 최대공약수와 최소공배수 구하는 공식 그대로 생각해서 구현해서 풀었다. import java.util.Scanner; //최대공약수와 최소공배수 public class Baek_2609 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int num1 = in.nextInt(); int num2 = in.nextInt(); int commonDivisor = 1; //최초 최대공약수 1로 설정 //두 수중 작은 수에서부터 돌면서 공약수를 확인 for (int i = Math.min(num1, num2); i > 1; i--) { /*만약 i가 num1과 num2의 공약수이..