kittae 님의 블로그

에라토스 테네스의 체의 알고리즘을 안다면 매우 쉽게 구현이 가능하다! 시간복잡도, 메모리 제한은 에라토스 테네스의 체의 시간 복잡도가 O(n*log log n)이기 때문에 충분하다고 판단했다.내가 생각한 로직은 이렇다에라토스 테네스의 체 알고리즘 사용arr[M] ~ arr[N]의 배열에 소수 판별 후 출력 [최종코드]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeniz..

에라토스 테네스의 체란?여러 개의 수가 소수인지 아닌지 판별할 때 사용하는 대표적인 알고리즘이다.소수를 구하는 가장 기본적이고 이해하기 쉬운 방법 중 하나이다. 어떻게 동작하는가?리스트 생성: 2부터 원하는 최대 숫자 N까지의 리스트를 만듦첫 번째 소수 선택: 가장 작은 소수인 2부터 시작배수 제거: 선택한 소수의 배수를 리스트에서 제거하거나 표시다음 소수 찾기: 리스트에서 다음으로 남아있는 수를 선택하고, 이 수의 배수를 제거반복: 이 과정을 N의 제곱근까지 반복  시간 복잡도는??에라토스테네스의 체의 시간 복잡도는 놀랍게도 O(N log log N)이다.log log N은 매우 천천히 증가하는 함수로, N이 실용적인 범위 내에서는 거의 상수에 가깝다.즉, 해당 알고리즘은 사실상 선형 시간에 가까운 ..

기본적인 소수 찾기 문제이다! 매우 쉬운 문제이며 필자는 예전에 소수문제를 에라토스테네스의 체를 공부해서 푼 기억이 난다.이참에 다시 복습할 겸, 간단한 문제여도 해당 알고리즘을 사용하기로 결심했다! 에라토스테네스의 체는 시간복잡도가 O(n * log  long n)이기 때문에 더더욱 시간 복잡도는 충분하다고 생각했다.또한 N의 수가 1000개 이하의 자연수라는 점에서 메모리 제한도 충분하다고 생각했다. 이번에는 로직은 따로 없다. [최종코드]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ne..

필자는 백준허브를 잘 사용하다가, 어느 순간 깃허브에 내가 푼 문제들이 업로드되지 않는다는 것을 느꼈다! 그래서 인터넷에 쳐보니, CORS관련 오류로 인해 업로드 오류가 생긴다고 한다. 해결법 1 - Modesif Origin Modesif Origin을 다운받고, CORS를 ON 해봤다! 하지만,,, 나는 실패,, 해결법 2 - Allow CORS똑같이 Allow CORS를 다운받고, off 상태에서 3번 Access-Control-Allow-Headers 체크하기! 결과는 또 실패,, 돌고돌아 포기하고 있었는데,, 나는 해당 오류가 뜰 무렵에 팀프로젝트를 하고 있었다.  ModHeader에 Token값을 넣어 JWT 사용을 위해 다운로드한 건데, 해당 Token이 꼬여서 그런 게 아닌가 싶었다! 혹..

문제 자체는 쉬웠지만, 문제 해석을 잘못 해석해 애먹은 문제였다..! 먼저 내가 생각한 로직은 이렇다.while(n ArrayList 적재for (sum += ArrayList.get(i))sum == num -> 약수 합 출력sum != num -> n is NOT perfect 출력 해당 로직을 보면 알다시피 완전수를 구하는 문제였는데, 필자는 그냥 테스트 케이스만 보고 순서대로 반복문으로 약수의 누적합을 비교해서 출력해 버린 것이었다! (맙소사,,) 먼저 내가 처음 작성한 코드다.import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { ..

해당 문제도 쉬운 문제였다! 해당 문제는 시간 복잡도와 메모리 제한은 10,000개 이하이기 때문에 신경 안 써도 된다고 판단했다! 내가 생각한 로직이다.for (i = 0; i 배열에 i값 적재출력값에 arr[k-1]값 출력 여기서 생각한건, 기본적인 arr를 사용한다면 k번째의 값을 구하는 로직이 복잡해지기 때문에 ArrayList로 구현했다![최종코드]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in..

이번 문제는 배수와 약수 문제로 쉬운 문제였다! 여기서 의문이 있었는데, 만약 예시로 15 15라고 했을 때, 약수와 배수 둘 다여서 고민을 했지만, 문제를 잘 보면 두 수가 같은 경우는 없다고 제약조건이 있었다! 시간제한과 메모리제한은 테스트 케이스가 작아 신경 안 써도 된다고 판단했다! 내가 생각한 로직이다.token2 % token1 == 0 -> factortoken1 % token2 == 0 -> multiple아니면 neither [최종 코드]import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader b..

구현 자체는 쉬운 문제였지만, 문제 자체가 나에겐 어려운 문제였다. 진법 변환에 미숙한 나에게는 굉장히 어려웠다. 급하게 해당 진법 변환에 대해 공부한 뒤, 문제를 풀게 되었다. 시간제한과 메모리 제한은 신경 안 써도 된다고 판단했다. 내가 생각한 로직이다.10진법이 문제.만약 ZZZZZ라면, Z = 35, 아스키코드로는 90, 즉 -55만약 0 ~ 9라면, 아스키 코드는 -48 or -'0' 해당 문제를 푸려면 아스키 코드와 진법에 대해 잘 알아야 되는 게 포인트다! 최종코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buf..