시간복잡도 생각해보기10^6이 최댓값이므로 O(NlogN)안에 해결하는 것이 중요하다.배열을 정렬하고 -> O(NlogN) + N-1개의 차를 계산하고O(N) +O(N-K)만큼 차를 더하므로 =>O(NlogN)풀이 아이디어K개의 집중국이 있을 때 연속된 센서 간의 차를 최소한으로 해라 => 그리디센서 좌표 배열을 받아서 연속된 센서 간의 차를 구한다.연속된 센서 간의 차이를 오름차순으로(혹은 내림차순)으로 정렬한다.집중국 개수 K-1 만큼만 배열들을 더해준다.집중국 K를 세워야 한다면 센서와 센서 사이를 K-1 회 뛰어넘을 수 있기 때문이다. 그리고 자기 자신에만 집중국을 세운다면 거리가 0이 되는 것도 생각해야 한다.의사코드 / 풀이 과정for(int i=0; i참고 자료
분류 전체보기
시간복잡도 생각해보기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..
엔지닉스에 CORS 처리를 위한 Preflight 요청이 계속 204로 채가지길래 응 ?? 왜저러지?? 했는데 83.97.131.110 - - [02/Dec/2024:03:04:09 +0000] "OPTIONS /policy/bookmark/request HTTP/1.1" 204 0 "http://localhost:5173/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36"183.97.131.110 - - [02/Dec/2024:03:04:44 +0000] "OPTIONS /policy/bookmark/request HTTP/1.1" 204..
유클리드 알고리즘은 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으로 대입하고, 과정을 반복한다.유클리드 호제법으로 최..
