3월 16일 Day11.

음.. 소수 구하는 알고리즘이 이렇게 방법이 다양했다라.. 난 그동안 무엇을 공부한 것인가..? 라는 의문이 들 정도로 모르는 것이 너무 많고 해야할 부분이 너무 너무 너무 많다. 일단 소수 구하는 것이 단순히 알고리즘 문제를 풀기 위해 배운 것이 아니라 암호화와 관련이 있어서 그만큼 중요하다는 것도 처음 알게 되었고 굉장히 많은 부분을 공부해야만 소수를 구할 수 있다는 것을....... 알았다.... 갑자기 내가 이 많은 것들을 할 수 있을 지 걱정이 되어버린 하루쓰 ~

하지만 해내야지? 어쩔티비

---

• 오늘의 목표 :: 아이디어 떠올리고 코드 구현 해보기, 많은 고민 하기, 하지만 너무 어려운 문제는 과감히 넘기기

 

• T.I.L

<자료구조 & 알고리즘>

 

* 소수

 

'소수'가 중요한 이유 ? "암호" 때문

참조 :: https://st-lab.tistory.com/81

JAVA [자바] - 소수 구하는 알고리즘 및 구현

1. N보다 작은 자연수로 모두 나눠본다. => O(N^2)

2. √N 이하의 자연수들로 모두 나눠본다. => O(N√N)

3. k=2 부터 √N 이하까지 , 자연수 중 k를 제외한 k의 배수를 제외 시킨다 (에라토스테네스의 체) => O(N logN(log N))

 

 

** 소수 구하기 : 1 ~ 1000 사이의 소수를 모두 출력

소수의 조건  → n % n == 0 && n % 1 == 0

↓ version 01↓

class PrimeNumber1 {
    public static void main(String[] args) {
        int counter = 0; // 나눗셈 횟수 확인 변수 (이 알고리즘의 처리 비용을 확인하려고 설정)

        for (int n = 2; n <= 1000; n++) {
            int i;
            for (i = 2; i < n; i++) {
                counter++;
                if (n % i == 0) // 나누어 떨어지면 소수가 아니다
                    break;      // 더이상 반복 필요 X
            }
            if (n == i)         // 마지막까지 나누어떨어지지 않음? 소수.
                System.out.println(n);

        }
        System.out.println("나눗셈 시행 횟수 : " + counter);
    }
}

나눗셈 시행 횟수 : 78022

결론 : 소수는 2부터 n-1까지 어떤 소수로도 나누어떨어지지 않는다. 

         ∴ n이 소수인지 알고 싶다면 n보다 작은 소수로만 나눗셈을 시행해도 된다.

 

 

↓ version 02↓ 

class PrimeNumber2 {
    public static void main(String[] args) {
        int counter = 0;                        // 나눗셈 횟수
        int ptr = 0;                            // 찾아낸 소수의 개수
        int[] prime = new int[500];             // 소수를 저장해둘 배열

        prime[ptr++] = 2;                       // 2는 소수임

        for (int n = 3; n <= 1000; n += 2) {    // 대상은 홀수만
            int i;
            for (i = 1; i < ptr; i++) {         // 이미 찾은 소수로 나눗셈 시행
                counter++;
                if (n % prime[i] == 0)          // 나누어떨어졌다? 소수가 아니다
                    break;
            }
            if (ptr == i)                       // 마지막까지 나누어 떨어지지 않았다? 소수다
                prime[ptr++] = n;               // 소수 배열에 저장
        }

        for (int i = 0; i < ptr; i++) {         // ptr개의 소수를 출력
            System.out.println(prime[i]);
        }
        System.out.println("나눗셈을 수행한 횟수 : " + counter);
    }

}

나눗셈 시행 횟수 : 14622

결론 : 빠른 알고리즘은 많은 메모리가 필요하다.

 

↓ version 03↓ 

소수는 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다. 

class PrimeNumber3 {
    public static void main(String[] args) {
        int counter = 0;                        // 곱셈과 나눗셈 횟수
        int ptr = 0;                            // 찾아낸 소수의 개수
        int[] prime = new int[500];             // 소수를 저장해둘 배열

	// 배열의 크기 = 500 인 이유? : 2 이외에 짝수는 소수가 아니다 so, 최소 절반을 준비하면 저장할 수 있다
                                                
        prime[ptr++] = 2;
        prime[ptr++] = 3;                       // 2, 3 은 소수이므로 미리 초기화

        for (int n = 5; n <= 1000; n += 2) {    // 5부터 홀수만 판단 시작
            boolean flag = true;                // flag가 true 이면 소수, false 면 소수 아님
            for (int i = 1; prime[i] * prime[i] <= n; i++) {
                counter += 2;
                if (n % prime[i] == 0) {        // 나누어 떨어진다? 소수가 아님
                    flag = false;
                    break;
                }
            }
            if (flag) {                         // flag == true == 소수
                prime[ptr++] = n;               // prime 배열에 저장
                counter++;
            }
        }

        for (int i = 0; i < ptr; i++) {
            System.out.println(prime[i]);
        }
        System.out.println("곱셈과 나눗셈을 수행한 횟수 : " + counter);
    }
}

나눗셈 시행 횟수 : 3774  (→ 성능이 좋아진 것을 확인)

*** 소수 관련하여 문제 더 풀어볼 것⭐⭐⭐⭐⭐

---

* 다차원 배열 (multi-dimensional array) 

다차원 배열 이용하여 ↓ 한 해의 경과 일 수를 계산하는 프로그램 만들기 ↓

class DayOfYear {
    // mdays 배열에 각 달의 일수를 저장하는데 윤년이 있는 2월의 요소를 28, 29로 생성
    static int[][] mdays = {
            {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, // 평년
            {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}  // 윤년
    };

    // 서기 year년은 윤년인가? 윤년 : 1 / 평년 : 0
    static int isLeap(int year) {
        return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) ? 1 : 0;
    }

    static int dayOfYear(int y, int m, int d) {
        int days = d;

        for (int i = 1; i < m; i++)
            days += mdays[isLeap(y)][i - 1];
        return days;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("그 해 경과 일수를 구합니다.");

        System.out.print("년 : ");        int year = sc.nextInt();
        System.out.print("월 : ");        int month = sc.nextInt();
        System.out.print("일 : ");        int day = sc.nextInt();

        System.out.printf("그 해 %d일째입니다.\n", dayOfYear(year, month, day));

    }
}

 

 

• 오늘 푼 문제

정수삼각형 :: https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

소수 찾기 :: https://www.acmicpc.net/problem/1978

1978번: 소수 찾기