23-06-02 TIL

문제

1. 백준 17103 (골드바흐 파티션)
   1-1. ArrayList를 선언 후, 메서드 3개를 만들어서 사용
   -> 1. 소수인지 확인하는 메서드
   -> 2. 소수인지 확인되면 ArrayList에 저장하는 메서드
   -> 3. ArrayList에 저장된 소수들끼리 더해서 원하는 값이 나오는 지 확인하는 메서드
   1-2. 시간초과
   -> 메인 메서드에도 for문 하나, 나머지 메서드들도 각각 1, 1, 2개씩 for문이 있어서 생기는 듯
2. 백준 13909 (창문 닦기)
   2-1. 예제 입력, 출력에는 같은 값이 나오지만 제출하면 메모리 초과가 계속 뜸
   -> 기존에 만들어 둔 ArrayList 에다가 입력만큼의 사이즈를 지정해서 전부 false로 두고, for문 두 개 사용해서 계속 증가시키면서 나눈 다음 나눠지면 true -> false, false -> true로 바꾸도록 하고 count를 세는 방식으로 했는데...
   -> 알고리즘을 다른 거를 생각해야하는지, 메모리 초과를 해결해야하는지 모르겠음

시도

1. for문과 같은 loop를 사용하지 않고 구현하도록 시도 (사용한다면 메인에서 1개만)
   1-1. 근데 소수인지 확인하려면 반복문을 사용하기는 해야해서...
   -> 최대 반복문 2개까지 하고 케이스를 줄여보고자 시도
   1-2. 메서드를 여러개 만들기보다 그냥 ArrayList를 100만개짜리 사이즈로 만들어서 소수인지 확인할까?
   -> 너무 하드코딩식이지만 더 이상 방법이 생각나지 않음 -> 시도
   1-3. Boolean 타입의 ArrayList를 만들고 그냥 0부터 1백만까지를 소수면 true, 아니면 false를 add 해줌
2. 둘 다 시도 해보자
   2-1. 메모리 초과 해결 시도
   2-1-1. 값이 21억개 정도 될 수 있으니까 int도 괜찮을 거라 생각했는데, 아닐 수도 있어서 double로 변경해봄
   -> 안됨
   -> Map으로도 변경해보고, linkedlist로도 해보고... 기타 등등의 방법으로 많은 시간을 들였지만 메모리 초과가 해결이 안됨...
   2-2. 뭔가 다른 알고리즘을 생각해보자
   2-2-1. 창문 숫자를 세봄
   2-2-2. 1명이면 1개, 2명이면 1개, 3명이면 1개, 4명이면 2개, 5명이면 2개, 6명이면 2개, 7명이면 2개, 8명이면 2개, 9명이면 3개...?? 뭔가 제곱근 반내림인거 같은 생각이 든다.
   2-2-3. 예제로 나온 24개면 4개... 아까 만들어둔 알고리즘으로 하면 25개면 5개...
   2-2-4. 제곱근 인거 같음.

해결

1. for문을 통해서 입력 값의 절반까지를 종료 조건으로 두고, 두 수를 더했을 경우 두 수가 ArrayList에서 둘 다 true 인지 확인
   -> isPrime이라는 소수인지 확인해주는 메서드에서 만약 2랑 3이면 그냥 true를 더해줌
   -> 해결
2. 해당하는 숫자의 제곱근의 정수 값이 답이였다.

알게 된 점

1. 기본적으로 반복문이 3 중첩이 되면 무조건 시간초과라는 것
   -> 처음에 시도하려고 했던 방법도 괜찮은 방법이라는 생각이 들긴하는데... 나중에 반복문을 줄이는 방안을 생각해서 구현해봐야겠다.
   1-1. 내가 소수인지 확인하는 방법을 사용할 때에 사용한 방법이 이름이 있었네... 그냥 어디서 기억나는 거였는데... => "에라토스테네스의 체" => 그냥 그럴 것이다라고 생각했는데 증명까지 해놓은 대단한 알고리즘임

• 베르트랑 공준
  - 임의의 정수 n >= 2 에 대하여 n < p < 2n 인 소수 p가 항상 존재한다.
• 골드바흐의 추측
  - 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다
• 에라토스테네스의 체
  - 소수가 되는 수의 배수를 지우면 남은 건 소수가 된다

  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
  2. 소수가 되는 수의 배수를 지우면 남은 건은 소수만 된다
  3. 자기 자신을 제외한 2의 배수를 모두 지운다.
  4. 남아 있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
  5. 자기 자신을 제외한 3의 배수를 모두 지운다.
  6. 남아 있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
  7. 자기 자신을 제외한 5의 배수를 모두 지운다.
  8. 위 과정을 반복한다.

=> 진짜 이런거(위에거 세개)는 처음 들어봤다.

2. 뭔가 소수, 약수 이런 파트여서 그렇게 해야하나 싶었는데 다른 방법이 있었다.
   -> 근데 메모리 초과를 해결하지 않고 다른 방법으로 해결했는데, 메모리 초과를 해결해서 푸는 방법이 있을지 궁금... 알아봐야겠음.

오늘 푼 문제

백준 1929 (소수 구하기) - Java

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        long num1 = Long.parseLong(st.nextToken());
        long num2 = Long.parseLong(st.nextToken());

		// 소수인지 확인
        // 1이면 넘기고, 2면 출력하고 넘긴다.
        for (long i = num1; i <=num2; i++) {
            if (i == 1) continue;
            else if (i == 2) {
                bw.write(String.valueOf(2) + "\n");
                continue;
            }
            if (isPrime(i))
                bw.write(String.valueOf(i) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

	// 소수면 true, 아니면 false를 return 해주는 메서드
    public static boolean isPrime(long num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0)   return false;
        }
        return true;
    }
}

백준 4948 (베르트랑 공준) - Java

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// 입력할 숫자
        long num1 = -1;
        while(true) {
            num1 = Long.parseLong(br.readLine());
            // 0 입력시 break;
            if (num1 == 0)  break;
            long count = 0;

            for (long i = num1 + 1; i <= num1 * 2; i++) {
                if (i == 1) continue;
                else if (i == 2) {
                    count++;
                    continue;
                }
                else if (isPrime(i)) count++;
            }
            bw.write(String.valueOf(count) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
	// 소수인지 확인해주는 메서드
    public static boolean isPrime(long num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0)   return false;
        }
        return true;
    }
}

백준 17103 (골드바흐 파티션) - Java

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int test_case = Integer.parseInt(br.readLine());
        ArrayList<Boolean> savePrime = new ArrayList<Boolean>();
        savePrime.add(false);
        savePrime.add(false);

        for (int i = 2; i < 1000001; i++) {
            if (isPrime(i)) {
                savePrime.add(true);
            }
            else savePrime.add(false);
        }

        for (int i = 0; i < test_case; i++) {
            int temp = Integer.parseInt(br.readLine());
            int count = 0;
            for (int j = 2; j <= temp / 2; j++) {
                if (savePrime.get(j) && savePrime.get(temp - j)) count++;
            }
            bw.write(String.valueOf(count) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
    public static boolean isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num) + 1; i++) {
            if (num == 2)   return true;
            else if (num == 3)  return true;
            else if (num % i == 0)   return false;
        }
        return true;
    }
}

백준 13909 (창문 닫기) - Java

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int test_case = Integer.parseInt(br.readLine());

        int cnt = 0;

        for(int i = 1; i <= Math.sqrt(test_case); i++) cnt++;

        bw.write(String.valueOf(cnt));

        bw.flush();
        bw.close();
        br.close();
    }
}