태화의 일기장

1. 문제 번호 11653

2. 문제 풀이

한줄 평가

•   이게 브론즈 1이야? 난 왜 브론즈 2~3의 수학문제가 더 어렵냐 ..?
•   소인수분해의 성질을 외우자!!! (추가개념 참고)

문제를 먼저 정확히 파악

• 소인수분해
  • 어떤 N을 소수들의 곱으로 나타내는 것이다. 
    예를 들어 28을 소인수분해 하면 2*2*7 이다.
• 소수
  • 1과 자기 자신만을 약수로 가지는 수를 말한다.
    cf)에라토스테네스의 체

나의 문제풀이 방식 및 순서

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

3. 소스 인증

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        
        for(int i = 2; i <= Math.sqrt(N); i++){
            while(true){
                if( ( N % i) != 0) {
                    break;
                }else {
                    System.out.println(i);
                    N /= i;
                }
            }
        }
        if (N > 1) {
            System.out.println(N);
        }
    }
}

- 실패 소스코드 -

4.추가 개념

소인수분해의 성질

•  소인수분해에서 인수 중 하나는 반드시 sqrt(N)보다 작거나 같다.
  (근데 난 왜 이렇게 표현하는지 모르겠네..)
  (하나는 반드시 작거나 같다가 뭐야? 하나만 작거나 같다라는 뜻인가? 28 의 경우 2 * 2 * 7인데)
  
•  sqrt(N)보다 큰 인수는 최소 0개 최대 1개이다. (<<이게 더 깔끔하지 않나? 

왜 인수 중 하나는 반드시 sqrt(N)보다 작거나 같을까?

 소인수분해는 어떤 수 N을 소수의 곱으로 표현하는 것이다. N = 100 이면 100 = 2 × 2 × 5 × 5 의 소수의 곱으로 나타낸다.

 이를 이해하기 위해 다음을 확인해보자.

1. 인수의 성질
   •  N 을 두 개의 인수  a 와  b 로 나타낼 수 있습니다. 즉,  N = a × b .
   • 여기서  a 와  b 는  N 의 인수입니다.
   
   
2. 최대 인수의 크기
   • 만약  a 와  b 가 모두  sqrt(N) 보다 크다면, 두 인수의 곱  a × b 는  N 보다 커집니다. 이는  N 을 초과하므로 불가능합니다
   
   
3. 결론
   • 따라서  N 의 인수 중 적어도 하나는 반드시  sqrt(N) 보다 작거나 같아야 합니다.

그래서 sqrt(N) 까지의 소수만 고려하면 충분하다.

5. 참조 블로그

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.

1. 문제 번호 2581번

2. 문제 풀이

한줄 평가

•   여전히 배열을 핸들링 하는 것은 까다롭다.
•   에라토스테네스의 이중 for문을 자유롭게 사용할 정도로 익숙해져야 한다.
    ( 꼭 1978번이랑 동일하게 갈 필요는 없다는 말이다. )
  
  • 처음 for문은 2부터 4의 배수부터 시작
  • 두번째 for문은 범위를 지정한다. 60~100까지  

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

   또.. 2시간 짜리 헛고생을 지독하게 했다.

1. 두가지 수를 입력받는다. 60~100, 1~5
2. 배열 0~(N-M)까지 만든다. (0인덱스를 Value = 60이라고 가정)
3. Math.max(i * i, ((M + i - 1) / i) * i);  
4. isPrime[j - M] = false;  로 (60-60)가 0인덱스를 말하니깐 초기화 해준다.
   
   

3. 소스 인증

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine()); //최소값
        int N = Integer.parseInt(br.readLine()); //최대값

        primeNumberSieve(M, N);
    }
    public static void primeNumberSieve(int M, int N){
        // +1 을 해주는 이유는?? >>10 - 5 = 5 그러면 0 = 5 , 1 = 6 , 2 = 7 , 3 = 8 , 4 = 9 가 되면서 5 = 10 이 빠지게 된다
        int length = N - M + 1; // 10 - 5 = 5 인데  5~10까지는 6개의 숫자
        boolean [] isPrime = new boolean[length];
        Arrays.fill(isPrime, true); //소수를 모두 true 로 초기화
        
        // Setting non-prime for 0 and 1 explicitly
        if (M == 0) isPrime[0] = false; // 0은 소수가 아니다
        if (M == 1) isPrime[1 - M] = false; // 1은 소수가 아니다


		//i*i를 하는 이유는 이미 작은 소수에서 제곱근들은 다 삭제가 되어버리기 때문에
        //아래 2 문장이 가장 중요한 에라토스테네스의 채
        for(int i = 2; i * i < N; i++){ 
            int start = Math.max(i * i, ((M + i - 1) / i ) * i); 
            /*
                i = 2 일때 60보다 큰 숫자이면서 2의 배수는 60 부터
                i = 3 일때 60보다 큰 숫자이면서 3의 배수는 60 부터
                i = 7 일때 60보다 큰 숫자이면서 7의 배수는 63 부터
            */


            /* j = j + i 로 배수 시작 */
            for(int j = start; j <= N; j += i){ //소수 2부터 시작하는게 아니라 4부터 시작하게 만든다.
                isPrime[j - M] = false; //소수인 것들은 제거
            }
        }

        boolean isPrimeFound = false; //최소 소수를 찾기 위한 변수
        int minValue = Integer.MAX_VALUE; //최소 소수를 찾기 위한 변수, 0으로 두면 초기값을 유지하기 때문에 헷갈린다.
        
        int sumIsPrime = 0; //소수의 합

        for(int i = 0; i < length; i++ ){
            if(isPrime[i]){
                sumIsPrime += M + i;

                if(!isPrimeFound){ //최소 소수값을 찾기 위한 변수
                    isPrimeFound = true;
                    minValue = M + i;
                }
            }
        }

        if(isPrimeFound){
            System.out.println(sumIsPrime);
            System.out.println(minValue);
        } else {
            System.out.println(-1);
        }
        
    }
}

- 실패 소스코드 -

4.추가 개념

에라토스테네스의 체

• 개념 : 여러개의 소수를 한 꺼번에 판별하고자 할 때 사용

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        System.out.println(isPrimeNumber(57));
    }
    static boolean isPrimeNumber(int i){
        for(int j = 2; j < i; j++){
            if( i % j == 0 ) return false;
        }
        return true;
    }
}

소수를 판별하기 위해 제일 간단하게 생각할 수 있는 소수 판별 알고리즘이다. 다만 for문을 2부터 n-1까지 모두 순차적으로 돌아야 하기 때문에  O(N)의 시간 복잡도를 가져 비효율 적이다. (앞선 알고리즘을 전부다 이렇게 풀었기 때문에 이제는 동영상 강의를 들어야 할 것 같다고 생각이 듬)

사실은  \(O(N\tfrac{1}{2})\)로 해결할 수 있다.

 소수는 1,2,3,5,7,11 과 같이 "1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수' 이다.

모든 약수는 대칭형태이다.

예를 들어 A가 12 일 때 A = 2×6, 3×4, 4×3, 6×2인데 √12 = 3.46 정도가 되므로 2~3까지만 확인 해보면 된다.

아래와 같이 참조하여 \(O(N\tfrac{1}{2})\) 로 계산이 가능하다.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        System.out.println(isPrimeNumber(97));
    }
    static boolean isPrimeNumber(int i){
        int end = (int)Math.sqrt(i);
        for(int j = 2; j <= end; j++){
            if( i % j == 0 ) return false;
        }
        return true;
    }
}

그렇다면 왜 에라토스테네스의 체를 배우는가?

이유는 여러 개의 소수를 한꺼번에 판별하고자 할때 사용하기 위해서 사용한다.

1.  시작부터 끝까지 배열을 만든다. (2~N까지)
2.  먼저 2의 배수를 지우며 본인은 Skip한다.
3.  3의 배수를 지우며 본인은 Skip한다.
4.  5의 배수를 지우며 보인은 Skip한다. (이미 4는 지웠기 때문에 건너뛴다.)

5. 참조 블로그

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.

1. 문제 번호 1978번

2. 문제 풀이

한줄 평가

•   특히나 배열의 index는 너무 헷갈리게 한다.
•   처음에 잘못 설계한 탓에 2시간 넘게 ..걸렸다.
  
  • 입력받은 1 3 5 7을 7까지 true,false로 초판 초기화하여 진행하려다가 맨 마지막에 잘못됨을 깨달았다.
• continue는 아래를 실행하는게 아니라 for문을 다시 실행 (당연하지만 실수를 했다.)

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

   2시간 짜리 헛고생을 지독하게 했다.

1. 1 3 5 7 을 배열 index 1 ~4까지 넣었다. ( ..?? 왜 그랬지.. 0에 다가 안넣으려고 별 짓을 다했다.)
2. 7까지 8자리 인덱스 배열에 boolean으로 다 만들었다.
3. 에라토스테네스 체를 사용
4. 남은것을 출력 ( 2 3 5 7 이 출력되버림..ㅡㅡ 2는 입력을 받지 않았으니 출력되면 안됐었다..)

3. 소스 인증

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
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 isPrimeCnt = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            boolean isPrimeYn = false;
            isPrimeYn = isPrime(Integer.parseInt(st.nextToken()));
            if(isPrimeYn) {
                isPrimeCnt++;
            }
        }
        System.out.println(isPrimeCnt);
        
    }
    public static boolean isPrime(int inputNum){
        if(inputNum < 2) return false;
        
        int end = (int)Math.sqrt(inputNum);
        for(int i = 2; i <= end; i++){
            if( (inputNum % i) == 0) {
                return false;
            }
        }
        return true;
    }
}

import java.util.*;
import java.lang.*;
import java.io.*;

/*
이 방법은 쓰지마세요 ㅋㅋㅋ
나의 문제풀이 방식 및 순서 보시면 잘못된 설계가 결과도 이상하게 만듭니다..
*/
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int inputCnt = Integer.parseInt(br.readLine());
        int [] inputAry = new int[inputCnt];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < inputCnt; i++) {
            inputAry[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(inputAry);
        primeNumberSieve(inputAry);
    }
    
    static void primeNumberSieve(int[] inputAry){
        // int maxValue = inputAry[inputAry.length-1];
        int maxValue = Arrays.stream(inputAry).max().getAsInt();
        
        boolean[] isPrime = new boolean[maxValue+1];
        Arrays.fill(isPrime,true); //모두 소수로 초기화
        isPrime[0] = isPrime[1] = false;
        
        /*에라토스테네스 체 사용*/
        for(int i = 2; i <= Math.sqrt(maxValue); i++){
            if(isPrime[i]){ //continue; //이미 지워진 숫자는 무시
                for(int j = i*i; j <= maxValue; j += i){ //배수는 삭제
                    isPrime[j] = false;
                }
            } 
        }

        int countPrimeNumber = 0;
        // for(int i = 0; i < isPrime.length; i++){
        //     if(isPrime[i]){
        //         countPrimeNumber++;    
        //     }
        // }
        for(int num : inputAry) {
            if(isPrime[num]) {
                countPrimeNumber++;
            }
        }

        
        System.out.print(countPrimeNumber);
        
    }
}

- 실패 소스코드 -

4.추가 개념

에라토스테네스의 체

• 개념 : 여러개의 소수를 한 꺼번에 판별하고자 할 때 사용

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        System.out.println(isPrimeNumber(57));
    }
    static boolean isPrimeNumber(int i){
        for(int j = 2; j < i; j++){
            if( i % j == 0 ) return false;
        }
        return true;
    }
}

소수를 판별하기 위해 제일 간단하게 생각할 수 있는 소수 판별 알고리즘이다. 다만 for문을 2부터 n-1까지 모두 순차적으로 돌아야 하기 때문에  O(N)의 시간 복잡도를 가져 비효율 적이다. (앞선 알고리즘을 전부다 이렇게 풀었기 때문에 이제는 동영상 강의를 들어야 할 것 같다고 생각이 듬)

사실은  \(O(N\tfrac{1}{2})\)로 해결할 수 있다.

 소수는 1,2,3,5,7,11 과 같이 "1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수' 이다.

모든 약수는 대칭형태이다.

예를 들어 A가 12 일 때 A = 2×6, 3×4, 4×3, 6×2인데 √12 = 3.46 정도가 되므로 2~3까지만 확인 해보면 된다.

아래와 같이 참조하여 \(O(N\tfrac{1}{2})\) 로 계산이 가능하다.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        System.out.println(isPrimeNumber(97));
    }
    static boolean isPrimeNumber(int i){
        int end = (int)Math.sqrt(i);
        for(int j = 2; j <= end; j++){
            if( i % j == 0 ) return false;
        }
        return true;
    }
}

그렇다면 왜 에라토스테네스의 체를 배우는가?

이유는 여러 개의 소수를 한꺼번에 판별하고자 할때 사용하기 위해서 사용한다.

1.  시작부터 끝까지 배열을 만든다. (2~N까지)
2.  먼저 2의 배수를 지우며 본인은 Skip한다.
3.  3의 배수를 지우며 본인은 Skip한다.
4.  5의 배수를 지우며 보인은 Skip한다. (이미 4는 지웠기 때문에 건너뛴다.)

5. 참조 블로그

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.