mojo's Blog

문제 링크 => https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 2~5,000,000 범위의 숫자들이 1~1,000,000 개가 주어질때 각각의 숫자들을 소인수분해하여 소인수들을 오름차순으로 출력하는 문제이다. 우리가 일반적으로 알고있는 factorize 의 시간복잡도는 O(N^(1/2)) 이므로 대략 5,000,000의 루트에 1,000,000을 곱한다면 2,236,067,977.499789... 이므로 시간초과가 난다는 것은 확실하다. 따라서 이..

특정 범위 내에서 소수를 전부 구하고 싶을때 효율적인 방법은 에라토스테네스의 체이다. O(N) 만큼의 Memory를 사용하여 O(Nlog(logN)) 만에 특정 범위 내의 소수를 전부 구할 수 있다. 에라스토테네스의 체를 구하는 Code bool is_prime[1000005]; void sieve() { for(int i=2; i

임의의 실수 x에 대하여 factorize 하는 방법 [2, N^(1/2)] 의 수들로 나눠 볼 때 나누는 수가 소수인지 확인할 필요가 없다!!! 만약에 N이 2로 나눠 떨어진다면 N값을 2로 나눠서 다시 2로 나눠 떨어지는지를 확인하고 그렇지 않은 경우 3으로 나눠 떨어지는지 확인하고 ... 반복한다. 이 과정을 반복하면 소수가 아닌 인수는 자연스럽게 없어지는 것을 확인할 수 있다. 따라서 Time Complexity O(N^(1/2)) 이 나온다. factorize 하는 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #defi..

파일을 읽어들여서 행맨(hangMan) 게임 만들기 import java.util.*; import java.io.*; class Word{ private String eng; Word(String eng){ this.eng=eng; } String getEng() { return this.eng; } } public class Main { static Vector v=new Vector(); static String randomWord() { int r=(int)(Math.random()*v.size()); return v.get(r).getEng(); } static void setPlay(boolean visited[], String eng) { for(int i=0;i

Scanner 를 이용하여 입력받은 데이터를 파일에 저장하는 프로그램을 작성하기 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); FileWriter fout=null; int c; try { fout=new FileWriter("c:\\Temp\\test.txt"); while(true){ String line=scanner.nextLine(); // line은 '\n' 이 들어가지 않음 if(line.length()==0) break; fout..

고객의 이름과 포인트 점수를 관리하는 프로그램을 해시맵을 이용하여 작성하는 문제이다. import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); HashMap h=new HashMap(); System.out.println("** 포인트 관리 프로그램입니다. **"); while(true) { System.out.print("이름과 포인트 입력>> "); String sentence=scanner.nextLine(); if(sentence.equals("그만")) break; String..