1978: 소수찾기

• 시간복잡도: 최악의 경우를 생각했을때 n^2으로도 풀 수 있다.
• 문제는 n개 수가 각자 소수인지를 찾아야한다.
  각 수는 1000이하의 수이다. 그러면
  최악의 경우의 수를 생각해보면
  1000번까지의소수판별을 100회를 진행해야한다.
  즉, 1000000정도의 시간이 필요하다.
  1초는 대략 1억이니 이정도면 충분하다.
• 공간복잡도: O(1)

풀이

소수: 2를 제외하고 인수가 1과 자기자신밖에 없는 수
가장 간단한 풀이를 생각해보면 2~자기자신까지 for문을 돌면서 비교를하는것이다
모두 돌아서 나누어진 수가 없다면, 그 수는 소수다
-> 만약 주어진수가 x이면 x번 반복을 해야한다.

풀이2

• 에라토스테네스의 체를 이용해보자
• 시간복잡도: nlog(nlogn)

• nlog(nlong)은 거의 n과 같을 것 같다.. log씌우면 값이 매우매우매우매우 작아지는 군!

풀이1 코드

import java.io.*;
import java.nio.Buffer;
import java.util.*;
// 1. 왜 static을 써야하는가?
// 2. 왜 main함수는 static인가?
// 3. 왜 statiac안에는 static을 써야하는가?
public class Main{
    public static boolean isSosu(int num){
        // 2는 소수입니다
        if(num==2) return true;
        // 2보다 작은 즉, 1은 소수가 아닙니다
        if(num < 2) return false;
        // 기본값을 true라고 설정해두고 조건을 위반하면 바로 함수를끝냄과 동시에 false를 return합니다
        boolean is = true; 
        for(int i=2;i<num;i++){ //1로는 무조건 나눠질것이니 2부터 시작을하고, 자기자신으로도 나눠질것이니 자기자신을 제외하고 반복문을 돌립니다.
            if(num%i==0){// 1과 자기자신을 제외하고 인수가 있다면, 이 수는
                return false;// 소수가 아닙니다
            }
        }
        // 반복문을 모두 조건에 부합하지 못했다면 그것은 소수가 맞습니다
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String input[] = br.readLine().split(" ");// 띄어쓰기를 기준으로 input을 나눕니다
        int count = 0; // 소수를 셀 변수를 만듭니다
        for(int i=0;i<n;i++){ // n번 만큼 반복합니다
            int num = Integer.parseInt(input[i]); // 띄어쓰기기준으로 숫자를 하나씩 가져옵니다
            // 하나씩 소수인지 판별합니다
            if(isSosu(num)) count++;//함수를 호출하지만 재귀적으로 호출되는게 아니기때문에 공간복잡도는 O(1)이다

        }
        //소수의 개수를 count합니다
        System.out.println(count);

    }


}

풀이2 코드

import java.io.*;
// 1. num까지의 수 중에 소수인수를 판별하고자 한다면 issosu[num]했을때도 제 값이 나와야한다
// 그러기 위해선 num+1개의 배열을 선언해주어야한다
// 2. num의 제곱근까지만 검사하면 되기때문에 i<num이 아니라 i*i<num까지만 계산하면된다
// 왜냐하면 i*i=num이라고 가정하자. 우리는 num*1=num까지 계산하려할것이다.
// 하지만 i*i=num을 기점으로 인수들은 i보다 작은값 + i보다 큰값으로 한 쌍을 이룰 것이다
// i보다 작은값은 분명 우리가 이전에 체크했던 값일것이다. 우린 1~i까지를 체크했을테니.
// 그렇기때문에 num의 제곱근까지만 체크하면 된다
// 3. 만약에 내가 보려는 i가 이미 소수가 아니라고 생각하자. 그 수는 이전에 그 수의 약수로 인해
// 그 수의 배수는 모두 체크가 된 이후일테니 이부분은 체크를 해주지 않아도된다
public class Main{
    public static boolean[] eratos(int num){
        boolean isSosu[] = new boolean[num+1];
        isSosu[0] = false;
        isSosu[1] = false;
        isSosu[2] = true;
        for(int i=3;i<num+1;i++){
            isSosu[i] = true;
        }

        for(int i=2;(double)i<=Math.sqrt(num);i++){
            if(isSosu[i]){
                for(int j=i+i;j<num+1;j+=i){
                    isSosu[j] = false;
                }
            }

        }




        return isSosu;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String input[] = br.readLine().split(" ");// 띄어쓰기를 기준으로 input을 나눕니다
        int count = 0; // 소수를 셀 변수를 만듭니다
        boolean isSosu[] = eratos(1000);
        for(int i=0;i<n;i++){ // n번 만큼 반복합니다
            int num = Integer.parseInt(input[i]); // 띄어쓰기기준으로 숫자를 하나씩 가져옵니다
            // 하나씩 소수인지 판별합니다
            if(isSosu[num]) count++;//함수를 호출하지만 재귀적으로 호출되는게 아니기때문에 공간복잡도는 O(1)이다

        }
        //소수의 개수를 count합니다
        System.out.println(count);

    }


}

1929: 소수구하기

접근

• 입력이 1,000,000 이기때문에 n^2으로는 풀 수 없다
  nlogn정도는 돼야한다 -> 에라토스테네스의 체 이용
• m이하의 소수 개수 - n이하의 소수 개수
• 단, n이 소수라면 + 1을 해준다
• 공간복잡도: O(n)

코드

import java.io.*;
public class Main{
    static boolean[] result(int n){
        //n이 들어올때 n이하의 수들에 대해서 소수인지 아닌지를 판별하기 위해 n이 아닌 n+1의 배열을 선언하였디
        boolean[] sosu = new boolean[n+1];
        //0이나 1은 소수가 아니다
        sosu[0] = false;
        sosu[1] = false;

        //일단 true라고 배열을 초기화한뒤에 소수가 아닌것들을 제거해나갈것이기때문에 일단 true로 배열을 세팅한다
        for(int i=2;i<=n;i++){
            sosu[i] = true;
        }

        //i=2부터 n의 제곱근까지한다. 이때 1 5 25 같이 제곱근이 들어있는 수가 있을수있으니 등호를 붙여준다
        for(int i=2;(double)i<=Math.sqrt(n);i++){
            //만약 2에 의해 2의 배수가 제거됐다. 그렇다면 4의배수는 제거할필요없다. 2의 배수중 4가 있기 때문에 2에의해 4의 배수는 제거됐을것이기 때문에
            if(sosu[i]){
                // 일단 j는 i*2부터 시작한다. 1부터 시작한다는 것은 소수인것 포함한 모든 수를 false로 만든다는 뜻이다
                // i의 배수인 j는 n보다 작거나 같아야한다. 같아야하는 이유는 1 5 25 같은 제곱근에 의해서 num이 되어버린 경우때문이며,
                // 큰 경우를 따지지 않는 이유는 당연하다. j보다 큰 값으로 j를 만들 수 없다(정수기준)
                // j는 i씩 증가해 나간다. i*2, i*3을 덧셈으로 표현한 결과이다
               for(int j=i+i;j<=n;j+=i){
                   sosu[j] = false;
               }
            }
        }
        return sosu;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");
        int m = Integer.parseInt((input[0]));
        int n = Integer.parseInt(input[1]);
        //가장 큰수 n이하에 대해서 각 수가 소수인지 아닌지를 써놓은 배열을 받아온다
        boolean[] sosu = result(n);

        // 범위에대해서 소수인 수만 출력해준다
        for(int i=m;i<=n;i++){
            if(sosu[i]) System.out.println(i);
        }


    }


}

8393: 합

접근

• 시간복잡도: 10,000*10,000 이더라도 1억을 안넘어서 n^2으로 풀 수 있다
• 공간복잡도: O(1)
• 직관적으로 푼다. 하나씩 더하고 출력한다

풀이1 코드

• O(n)

import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException {
        // 가장 직관적인 풀이
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int sum = 0;
        // 1부터 n까지의 합을 출력한다
        for(int i=1;i<=n;i++){
            sum+=i;
        }
        System.out.println(sum);
    }


}

풀이2코드

• O(1)

import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println((n*(n+1)/2));
    }


}

질문

왜 main함수는 static인가?