시간복잡도 생각해보기10의 최대가 5승이기 때문에 O(NM)으로 풀수 없고 O(NlogM)으로 풀어야 하는 문제였음.반복문 M번 동안 우선순위 큐를 사용하고 정렬하므로 O(MlogN)풀이 아이디어계속 최신으로 큰 값을 갱신해줘야 해서 우선순위 큐 사용M번 반복문 돌리며 아이들이 원하는 값보다 선물상자에 있는 값이 작으면 바로 0 리턴만약 무사히 M번동안 선물 조건이 충족했다면 1리턴의사코드 / 풀이 과정for(int i=0; igive) { //선물이 남았으면 hpq.add(maxBox - give); }} 틀린코드, 틀린이유import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Priorit..

시간복잡도 생각해보기N이 10^5 이므로, O(NlogN)에 끝내야한다.풀이 아이디어최소끼리 더하면 최소가 된다는 그리디적 상상을 해야한다.더해준 최솟값 합도 다시 더 해줘야 하므로 우선순위 큐에 넣어서 항상 최소상태 유지예를 들어 1,1,1,5 일때 1+1 을 하면 2가 되는데, 2,1,5가 아닌 1,2,5가 되어야 한다.더한 배열을 업뎃하고 정렬해주는 식으로 하면 메모리 초과가 난다.의사코드 / 풀이 과정배열을 받아서 우선순위 큐에 넣는다.가장 최소인 것들을 front에서 꺼내서(poll) 두개를 더한다.더해준 값들도 우선순위 큐에 다시 넣는다. (add)for(int i=0; i틀린 코드import java.io.BufferedReader;import java.io.IOException;import..

기본적인 정렬 문제였음.시간복잡도 생각해보기최대 N이 10의 5승이므로 O(logN)으로 해결 필요숫자 N개를 String으로 변환하기 -> O(N)숫자 두개를 더했을때 큰 것 정렬하기 -> O(logN)숫자 출력하기 -> O(N)총 O(logN)풀이 아이디어숫자를 모두 String값으로 만들고 두개를 더해서 큰 값이 되는 것을 정렬해주면 되는 문제였다의사코드 / 풀이 과정for(int num: numbers){ list.add(String.valueOf(num)); }Collections.sort(list,(a,b)->{ return (b+a).compareTo(a+b);});StringBuilder result = new StringBuilder();for(String..

유클리드 알고리즘은 2개의 자연수의 최대공약수를 구하는 방법이다.최대 공약수(GCD)어떤 두 수 A,B가 존재할 때, 공통인 약수 중 가장 큰 수를 말한다.EX) GCD(A,B) = A와 B의 최대공약수최소 공배수(LCM) 어떤 두 수 A,B가 존재할 때, 그들의 배수가 되는 가장 작은 수 최대 공약수(GCD) 구하는 방법  유클리드 호제법으로 최대 공약수 구하는 방법유클리드 호제법의 핵심은 모듈러 연산이다.모듈러 연산을 반복해서 0이 될 때까지 간다면 최대공약수를 구할 수 있다.1. A와 B중 더 큰수를 찾고, 큰수를 A로, 작은수를 B로 설정한다.2. A % B = N을 구해서, N==0이면 B는 최대공약수이다.3. N !=0 이면 A=B, B=N으로 대입하고, 과정을 반복한다.유클리드 호제법으로 최..

타일링 1 말고 2부터 한 나 멋있어 ..물론 풀이 봤지만이 문제가 DP라고는 생각도 못했다. 이 문제는 그림을 그려보면 된다. 타일 그림을 그러보면 N = 1 일 때는 1개,N = 2 일 때는 3개,N = 3 일 때는 5개,N = 4 일 때는 11개가 된다. 규칙 = 전전 수 * 2 + 전 수 = 현재 수 따라서 DP 점화식으로 표현하면,DP[N] = DP[N-1] + 2DP[N-2] 가 된다. 자바 코드 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Bj11727 { public static void main(String [] args) throws NumberFo..

이문제 푸는데 두시간이 걸림...import java.io.BufferedReader;import java.io.FileReader;public class sw1215 { static int T = 10; static char [][] arr; static int N; static int answer; public static void main(String [] args) throws Exception{ BufferedReader br = new BufferedReader(new FileReader("src/input (2).txt")); for(int test = 1; test(N-1)/2;j--) { sb2.append(arr2[j]); }// System.out.println("sb1: ..