학습용 공간

# 다이나믹 프로그래밍 : 큰 문제를 작은 나눠서 푸는 방식의 프로그래밍

 

# 큰 문제를 작은 나눠서 푸는 방법 2가지 : 다이나믹 프로그래밍(Dynamic Programming), 분할 정복 알고리즘(Divide & Conquer)

 

# 다이나믹 프로그래밍으로 풀 수 있는 문제들이 갖는 2가지 속성 : Overlapping Subproblem, Optimal Substructure

 

1. Overlapping Subproblem(겹치는 부분 문제) 

 - 큰 문제의 부분 문제들의 중복이 존재해야 한다.

 - 문제들이 겹치므로 큰 문제는 부분 문제들을 푸는 방법과 같은 방법으로 풀 수 있다. -> 주로 재귀를 사용

 

2. Optimal Substructure(최적 부분 구조) 

 - 큰 문제의 정답을 부분 문제의 정답을 통해 구할 수 있다.

 - 문제의 크기에 상관 없이 어떤 한 문제의 정답은 일정해야 한다.

 

ex) 피보나치 수를 구하는 방법 : F(n) = F(n-1) + F(n-2)

   큰 문제 : F(n), 부분 문제 : F(n-1), F(n-2)

   1. Overlapping Subproblem : F(n)을 구하기 위해 필요한 부분 문제 F(n-2)는 F(n-1)을 구하는데 필요한 부분 문제이기도 하다.(중복됨)

   2. Optimal Substructure : 부분 문제인 F(1)과 F(0)을 풀면 큰 문제인 F(2)를 풀 수 있고, 부분 문제인 F(n-1)과 F(n-2)를 풀면 큰 문제인 F(n)을 풀 수 있다.

 

# 다이나믹 프로그래밍의 방법 : 부분 문제들을 해결해서 얻은 답을 기록해둔다.(다시 연산할 필요가 없도록) -> Memorization

피보나치를 예로 들면 F(n)을 구하기 위해 F(0), F(1), ..., F(n-2), F(n-1)의 답들을 기록해둔다.

 

5번째 피보나치 수를 구하면서 풀게되는 부분 문제들이다. 

그림을 보면 중복되는 부분 문제들이 존재하는 것을 확인할 수 있다.

중복되는 부분 문제들을 맞닥뜨릴 때마다 연산하지 않고, 전에 풀고 기록해둔 답을 가져와서 쓴다면 큰 문제를 해결하는데 소요되는 시간을 줄일 수 있다.

public class Doodle {
    int[] memo = new int[100]; // memorization을 위한 기록 배열
    int fibonacci_with(int n) { // memorization 사용
        if (n <= 1) {
            return n;
        } else {
            if (memo[n] > 0) { // 전에 푼적이 있는 작은 문제라면
                return memo[n]; // 또 풀지 말고 기록해두었던 답을 가져와서 사용
            }
            memo[n] = fibonacci_with(n-1) + fibonacci_with(n-2);
            return memo[n];
        }
    }

    int fibonacci_without(int n) { // memorization 사용하지 않음
        if (n <= 1) {
            return n;
        } else {
            return fibonacci_without(n-1) + fibonacci_without(n-2);
        }
    }
}

위 함수는 memorization을 사용한 것, 아래 함수는 사용하지 않은 것임.

memorization을 사용하지 않은 알고리즘의 경우, 큰 문제를 1개 해결하기 위해 부분 문제 2개를 풀어야 하고 각 부분 문제를 풀기 위해서도 2개의 부분 문제를 풀어야 한다. 결국 n번째 피보나치 수를 구하기 위해서는 2*2*2*... = 2^n 만큼 문제를 푸는 연산을 해야 한다.

문제 1개를 푸는데 걸리는 시간이 O(1)이므로 

총 O(2^n)의 시간복잡도를 갖는다.

반면, memorization을 사용한 알고리즘의 경우, n번째 피보나치 수를 구하기 위해 문제 해결 연산을 n번만 수행하면 된다. 부분 문제들이 중복된다 하더라고 1번 연산을 수행했으면 그 답을 기록한 것을 사용하면 되기 때문이다. 

결국 총 O(n)의 시간복잡도를 갖는다.

memorization을 사용하지 않은 알고리즘에 비해 월등히 빠른 것을 확인할 수 있다.

 

# 다이나믹 프로그래밍의 구현 방식

1. Top-Down : 큰 문제를 조금씩 작게 만들어가는 것

 - 큰 문제부터 문제를 쪼개가면서 부분 문제들로 만드는 것을 반복하여, 부분 문제를 푸는 것으로 큰 문제를 해결

2. Bottom-Up : 작은 문제를 조금씩 크게 만들어가는 것

 - 부분 문제들을 모아서 큰 문제를 하나 만들어가는 것을 반복하며 큰 문제를 해결

   ex) 위의 피보나치 수를 구하는 알고리즘은 Bottom-Up 방식의 예이다.

 

두 방법에 시간 차이가 존재하는가? -> 단정지을 수 없다.

재귀를 사용하는 Top-Down이 더 오래걸릴것이라고 느낄 수 있다.

(재귀마다 변수들을 생성하고, 스택오버플로우 문제 발생 가능)

그러나 Bottom-Up 방식은 무조건 존재하는 모든 부분 문제들을 풀어야 큰 문제를 풀 수 있다는 단점을 가진다.

결국 어떤 방식이 시간이 더 적게 소요된다고 단정지을 수 없다.

 

다만 파이썬은 Bottom-Up을 추천하고

스택오버플로우 문제가 상대적으로 잘 발생하지 않는 C나 JAVA는 Top-Down을 추천한다. 

 

# 다이나믹 프로그래밍 문제 풀이는 점화식을 정의하는 것으로부터 시작한다.

 

 

해설은 주석 참고

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Double> operand = new Stack<>(); // 피연산자 스택
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 피연산자의 개수
        Double[] operandArray = new Double[n]; // 피연산자들을 저장하는 배열
        String cmd = sc.next(); // 수식 받아오기
        for (int i=0;i<n;i++) {
            operandArray[i] = sc.nextDouble(); // 입력받은 정수 피연산자에 할당
        }
        // 알파벳으로 입력받는 피연산자를 해당 알파벳에 할당되는 정수로 접근하기 위한 방법
        // -> ASCII 코드 사용
        // 각 알파벳은 A = 65, ..., Z = 90의 아스키 코드 값을 갖는다.
        // Character형을 int형으로 형변환 시키면 해당 아스키 코드 값을 반환한다.
        // ex) int('A') = 65
        // A는 첫번째로 입력받은 정수를 의미하므로 정수 저장 배열의 0번째 원소에 접근하면 된다.
        // 이를 수행하기 위한 방법 : operandArray[(int)입력된알파벳 - (int)'A']]
        // ex) C에 할당된 정수(배열의 인덱스 2번 원소) 접근하기
        // -> operandArray[(int)'C' - (int)'A']] 이는 곧 operandArray[2]와 같은 의미를 갖는다.

        for (int i=0;i<cmd.length();i++) {
            double operand_1, operand_2 = 0;
            switch (cmd.charAt(i)) { // 연산자가 들어올 경우 피연산자 스택의 상위 2개 항목을 연산하고 다시 push해줌
                case '+' :
                    operand_2 = operand.pop();
                    operand_1 = operand.pop();
                    operand.push(operand_1 + operand_2);
                    break;
                case '-' :
                    operand_2 = operand.pop();
                    operand_1 = operand.pop();
                    operand.push(operand_1 - operand_2);
                    break;
                case '*' :
                    operand_2 = operand.pop();
                    operand_1 = operand.pop();
                    operand.push(operand_1 * operand_2);
                    break;
                case '/' :
                    operand_2 = operand.pop();
                    operand_1 = operand.pop();
                    operand.push(operand_1 / operand_2);
                    break;
                default: // 피연산자라면
                    operand.push(operandArray[(int)cmd.charAt(i) - (int)'A']);// 피연산자의 정수값 stack에 넣어주기
                    break;
            }
        }
        System.out.printf("%.2f", operand.pop()); // 모든 연산을 처리한 후에 최종 결과는 피연산자 스택에 한개의 항목으로 남게 됨
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1935

2진수의 각 3자리는 8진수의 1자리로 변환된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String binaryNum = sc.nextLine();
        // 2진수를 8진수로 변환하면 2진수의 자리수 3개가 8진수 자리수 1개로 변환된다.
        if (binaryNum.length()%3 == 1) { // 2진수 가장 앞의 한자리가 8진수의 첫자리를 의미
            System.out.print(Character.getNumericValue(binaryNum.charAt(0))*1);
        } else if (binaryNum.length()%3 == 2) { // 2진수 가장 앞의 두자리가 8진수의 첫자리를 의미
            System.out.print(Character.getNumericValue(binaryNum.charAt(0))*2 +
                    Character.getNumericValue(binaryNum.charAt(1))*1);
        }
        // 2진수의 자리수가 3의 배수임
        for (int i=binaryNum.length()%3;i<binaryNum.length();i+=3) { // 2진수의 3자리를 8진수 1자리로 변환하기 때문에 i값은 3씩 늘어남
            // 각 2진수 3자리의 2^0자리는 *1, 2^1자리는 *2, 2^2는 *4를 해주고 모두 더하여 8진수 한자리를 구한다.
            System.out.print(Character.getNumericValue(binaryNum.charAt(i))*4 +
                    Character.getNumericValue(binaryNum.charAt(i+1))*2 +
                    Character.getNumericValue(binaryNum.charAt(i+2))*1);
        }
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1373

수빈이가 이동하는 방법은 +D 또는 -D 밖에 없다. -> 수빈이 동생을 찾기 위해서는 수빈과 동생과의 거리가 D의 배수여야 한다.

 

동생이 한명이라면? -> D = 수빈과 동생과의 거리의 약수이면 된다.

동생이 n명이라면? -> D = 수빈과 동생들과의 거리들의 공약수이면 된다.

D의 최대값 = 거리들의 최대공약수

 

즉, 최대공약수를 구하는 알고리즘을 사용하여 해결하면 된다.

 

최대공약수를 구하는 알고리즘은 유클리드 호제법을 사용했다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);;
        int n = sc.nextInt(); // 동생 n명
        int s = sc.nextInt(); // 수빈의 위치 = s

        int[] distance = new int[n]; // 수빈과 동생과의 거리 모음

        // 동생 n명과 수빈과의 거리들의 최대공약수를 구하면 D의 최대값이 된다.
        for (int i=0;i<n;i++) { // 거리 입력 반복문
            int position = sc.nextInt();
            distance[i] = Math.abs(s-position); // Math.abs : 절대값 구하는 메소드
        }
        int answer = distance[0];
        for (int i=1;i<n;i++) {
            answer = gcd(answer, distance[i]);
        }
        System.out.println(answer);
    }

    public static int gcd(int a, int b) { // 유클리드 호제법을 사용한 최대공약수 구하기
        while (b != 0) {
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/17087

팩토리얼에서 0의 개수란?

ex) 10! = 362800 -> 2개

 

팩토리얼에서 0의 개수를 구하는 방법은 팩토리얼의 인수에 2*5(10)이 들어있는 개수를 구하면 된다.

(0을 만들 수 있는 방법이 2*5밖에 없기 떄문)

인수들에서 5를 포함하는 수보다(5의 배수) 2를 포함하는 수가 더 많기 떄문에

5를 포함하는 인수들의 개수를 구해주면 팩토리얼에 들어가는 0의 개수를 알아낼 수 있다.

이 때, 5*5 또는 5*5*5처럼 5가 여러번 들어가는 경우도 고려해주어야한다.

 

ex)

입력이 100이라고 가정하면,

100/5 = 20 -> 5가 20번 들어감

100/25 = 4 -> 5가 2개 들어가는 경우는 4번

따라서 20 + 4 = 24

100!에 들어있는 0의 개수는 총 24개이다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int factorial = sc.nextInt();
        // 인수들 중 5의 개수가 2의 개수보다 많기 때문에 5의 개수를 세어주면 된다.
        int num_of_5 = factorial/5;
        int num_of_25 = factorial/25; // 5가 2개 들어가는 경우들 추가로 세어주어야 함
        int num_of_125 = factorial/125; // N의 범위가 500까지이므로 5개 3번 들어가는 경우(125)도 있을 수 있음
        System.out.println(num_of_5 + num_of_25 + num_of_125);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1676

소수의 개수를 파악하는데 에라토스체네스의 체를 사용했다.

에라토스체네스의 체는 2개의 단계를 반복 수행하는 것으로 이루어진다.

   1. 지워지지 않은 수 중에서 가장 작은 수 -> 소수이다.

   2. 1단계에서 구한 소수의 배수들을 모두 지원준다.
        // 해당과정 반복

설명은 주석 참고

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int sNum = sc.nextInt();
        int eNum = sc.nextInt();
        int[] prime = new int[eNum-sNum+1]; // 소수 저장
        int pn = 0; // 소수의 개수
        boolean[] check = new boolean[eNum+1]; // 에라토스체네스의 체 구현 (지워지면 true)
        // 소수의 개수를 파악하는데 에라토스체네스의 체를 사용
        // 에라토스체네스의 체는 2개의 단계를 반복 수행하는 것으로 이루어진다.
        // 1. 지워지지 않은 수 중에서 가장 작은 수 -> 소수이다.
        // 2. 1단계에서 구한 소수의 배수들을 모두 지원준다.
        // 해당과정 반복
        for (int i=2;i<eNum+1;i++) { // 들어온 정수들과 그 사이 정수들에 대해 소수 판별
            // 그 사이 정수들에 대한 것이라 하더라도 i=2부터 수행해주어야 소수들이 제대로 지워짐
            if (check[i] ==  false) { // 해당 수가 지워져 있는지 확인 (1단계)
                // 지워져 있지 않다면(false) 소수임
                if (i >= sNum) { // 시작 범위 보다 큰 정수만
                    prime[pn++] = i; // 구한 소수 배열에 넣어주고, 개수 갱신
                }
                for (int j=i+i;j<=eNum;j+=i) { // 구한 소수의 배수들을 모두 지워줌 (2단계)
                    // j 값은 i*2, ..., i(i+1), i(i+2), ...순으로 증가한다.
                    // j=i*i로 사용하면 시간을 더 단축할 수 있지만 
                    // 해당 문제의 입력의 범위에서 i는 최대 1,000,000까지 들어올 수 있다.
                    // 이 때 i*i는 java에서 int의 범위인 -2147483648 ~ 2147483647를 넘어가기 때문에 런타임에러가 발생하게 된다.
                    // 때문에 입력이 큰 수에 대해서는 j의 시작 값을 i+i 또는 i*2로 설정해주어야 한다.
                    
                    // j=i*i의 경우에 j 값이 i*2, ... 부터 시작하지 않는 이유는
                    // 예를 들어 i=6이라면 6보다 작은 수에 대한 배수들은 이미 지워졌기 때문이다. (i=2~5일 때 이미 각 배수들이 모두 지워졌으므로 이 과정을 스킵할 수 있음)
                    check[j] = true; // 해당 수 지우기
                }
            }
        }
        for (int i=0;i<pn;i++) {
            System.out.println(prime[i]);
        }
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1929

소수를 판별하기 위해서는 그 수가 소인수(자연수를 나누어 떨어뜨리는 약수 중 소수인 수)를 갖는 지 확인해야한다.

어떤 수가 소수가 아니라면, 그 수(N)는 N = a*b (a, b는 소수)꼴로 나타낼 수 있다.

이 때, a>b 라고 하면, a는 언제나 루트(N)보다 작은 값을 가지고, b는 루트(N)보다 큰 값을 가진다.

그러므로 루트(N)보다 작은 수에 대해서만 N이 나누어떨어지는지 확인하면 N이 소수인지의 여부를 파악할 수 있다.

반복문은 루트(N)번 반복되며 시간 복잡도는 O(루트(N))이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int num_of_prime = 0;
        for (int i=0;i<cnt;i++) {
            int num = sc.nextInt();
            if (checkPrime(num)) { // 소수 맞으면 조건문 들어감
                num_of_prime++; // 소수 개수 1개 추가
            }
        }
        System.out.println(num_of_prime);
    }

    public static boolean checkPrime(int num) {
        if (num < 2) { // 2보다 작은 소수는 없다.
            return false;
        }
        // i는 num이 소수인지 판별하기 위해 나누어주는 수(2부터 나누어주면 됨)
        for (int i=2;i*i<=num;i++) { //java에서 int의 범위는 -2147483648 ~ 2147483647 (num의 최대 입력인 1000을 충분히 수용가능)
            if (num%i == 0) { // 나누어 떨어지는 수가 존재한다면
                return false; // 소수가 아니다.
            }
        }
        return true; // 위 조건들을 모두 통과한다면 소수 맞음
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1978

최대공약수를 구하기 위해 유클리드 호제법을 사용했고

최소공배수를 사용하기 위해 구한 최소공배수 값을 활용했다.

cf) 유클리드 호제법 :

   GCD(a, b) = GCD(b, r)이다.

   이 때, r = a를 b로 나눈 나머지이다.
   r = 0이 될때, b가 최대공약수가 된다.
   ex) GCD(24, 16) = GCD(16, 8) = GCD(8, 0) -> 최대공약수 = 8

cf) 최소공배수 = gcd*(a/gcd)*(b/gcd)이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        int GCD = gcd(num1, num2);
        System.out.println(GCD);
        System.out.println(lcm(GCD, num1, num2));

    }

    public static int gcd(int a, int b) { // 유클리드 호제법 사용
        while (b != 0) {
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }

    public static int lcm(int gcd, int a, int b) {
        return gcd*(a/gcd)*(b/gcd); // 최소공배수 LCM = gcd*(a/gcd)*(b/gcd)이다.
    }
}

1. 나머지 연산

 - 덧셈 : (A+B)modM = ((AmodM)+(BmodM))modM
 - 곱셍 : (A*B)modM = ((AmodM)*(BmodM))modM

 - 뺄셈 : (A-B)modM = ((AmodM)-(BmodM)+M)modM

cf) 왜 덧셈, 곱셈과 달리 +M을 해주는가?
ex) ((6%3)-(5%3))%3 = -2%3 = ? 
이 답은 -2인가 1인가 -> 언어마다 답이 다르다. (Java, C는 -2, Python은 1이라고 답함)
이를 방지하기 위해 값이 음수로 나와도 이를 양수로 바꾸고 연산하기 위해 +M을 해주는 것임.

2. 최대공약수 GCD(Greatest Common Divisor), 최소공배수(Least Common Multiple)

int gcd = 1;
for (int i=2;i<min(a,b);i++) {
	if ((a%i == 0) && (b%i == 0)) {
    	g = i;
    }
}

작은 수부터 큰 수로 순서로 구하므로 최종적으로 구해진 공약수(gcd)는 최대공약수가 된다.

O(N)의 시간이 걸리는 알고리즘

 

# 유클리드 호제법

GCD(a, b) = GCD(b, r)
이 때, r은 a를 b로 나눈 나머지이다.
r = 0이 될때, b가 최대공약수가 된다.
ex) GCD(24, 16) = GCD(16, 8) = GCD(8, 0) -> 최대공약수 = 8

public int gcd(int a, int b) {
    if (b==0) { // r이 0이 된 상황 -> 이때 a 자리의 수가 최대공약수가 된다.
        return a;
    } else{
        return gcd(b, a%b); // 재귀함수를 사용하여 최대공약수가 나올때까지 연간
    }
}

public int gcd(int a, int b) { // 재귀함수를 사용하지 않은 유클리드 호제법
	while (b != 0) {
        int r = a%b;
        a = b;
        b = r;
    }
    return a;
}

O(logM)의 시간이 걸리는 알고리즘

 

최소공배수는 최대공약수를 이용하여 구할 수 있다.

LCM =  GCD*(a/GCD)*(b/GCD) 이다. 

 

3. 소수 (중요)

대표적으로 두가지 알고리즘이 존재한다.

1) 어떤 수 N이 소수인지 아닌지 판별하는 알고리즘

2) 어떤 수 N보다 작거나 같은 모든 자연수 중에서 모든 소수들을 찾아내는 알고리즘

 

1)  어떤 수 N이 소수인지 아닌지 판별하는 알고리즘

public class Main {
    public boolean prime(int n) {
        if (n < 2) { // 2보다 작은 소수는 없음
            return false;
        }
        for (int i=2;i<n-1;i++) {
            if (n%i == 0) { // 나누어 떨어지는 수가 있으면
                return false; // 소수 아님
            }
        }
        return true; // 위 판정을 통과하면 소수가 맞음 (나누어떨어지는 수가 없었음)
    }
}

위 알고리즘은 O(N)의 시간이 걸린다.

 

N이 소수가 되기 위해서는 2보다 크거나 같고 N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

이는 N에 대해 N/2보다 큰 수로는 절대 나누어 떨어지지 않는다는 것을 의미하기도 한다.

이를 활용하면

public class Main {
    public boolean prime(int n) {
        if (n < 2) { // 2보다 작은 소수는 없음
            return false;
        }
        for (int i=2;i<n/2;i++) { // n/2보다 큰 수로는 나누어떨어지지 않는다는 것을 알기 때문에 n/2까지만 확인
            if (n%i == 0) { // 나누어 떨어지는 수가 있으면
                return false; // 소수 아님
            }
        }
        return true; // 위 판정을 통과하면 소수가 맞음 (나누어떨어지는 수가 없었음)
    }
}

이렇게 O(N/2)의 알고리즘을 만들 수 있다. (하지만 O(N/2)도 결국은 O(N)..)

 

N이 소수가 아니라면, N = a*b꼴로 나타낼 수 있다. (이 때, a, b >= 2이다.)

a<=b이라고 할 때, a<루트(N), 루트(N)<b이다.

ex) 24의 약수에는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 여기서 a = 1,2,3,4 / b = 6,8,12,24 

    루트(N) = 4.xxx -> a < 4.xxx, 4.xxx < b

이에 따라 루트(N)까지만 검사를 해보면 N이 소수인지 판단할 수 있다.

public class Main {
    public boolean prime(int n) {
        if (n < 2) { // 2보다 작은 소수는 없음
            return false;
        }
        // 실수는 근사값이므로 사용하지 않는 것이 좋기 때문에 i<=루트(n) 대신 i*i<=n을 사용
        for (int i=2;i*i<=n;i++) { // 루트(n)까지만 검사를 하는 것. 
            if (n%i == 0) { // 나누어 떨어지는 수가 있으면
                return false; // 소수 아님
            }
        }
        return true; // 위 판정을 통과하면 소수가 맞음 (나누어떨어지는 수가 없었음)
    }
}

O(루트(N))의 시간이 걸리는 알고리즘

 

2) 어떤 수 N보다 작거나 같은 모든 자연수 중에서 모든 소수들을 찾아내는 알고리즘

1번의 알고리즘을 활용한다.

N을 기준으로 같거나 작은 소수를 구하려면, N개의 숫자에 대해 루트(N)이 걸리는 1번의 알고리즘을 사용해야 한다.

-> O(N루트(N))의 시간이 걸리는 알고리즘

 

이보다 빠른 방법은 에라토스테네스의 체를 사용한 방법이 있다. 

소수를 구하기 위한 가장 바람직한 방법 중 하나이다.

 

 

좌측의 표를 사용한다. (N=100 가정)

먼저, 지워지지 않은 수 중 가장 작은 수는 2이다.

그럼 2는 소수가 된다. 

그리고 2의 배수는 모두 소수가 아니기 때문에 표에서 전부 지워준다.

이렇게 지워지지 않은 수 중 가장 작은 수를 구하고, 그 수의 배수들을 전부 지우는 과정을 반복 수행하면 소수들을 구할 수 있다.

(해당 경우에서는 10번 반복)

(11*11 = 121 > 100이기 때문)

 

 

10번의 과정 반복을 통해 소수를 제외한 수들을 모두 제거한 모습이다.

 

 

 

 

 

 

 

 

 

 

 

 

public class Main {
    int[] prime = new int[100];
    int pn = 0; // 소수의 개수
    boolean[] check = new boolean[101]; // 소수가 아닌수가 지워지면 해당 칸을 true로 함 (boolean 초기 값은 false임)
    int n = 100;
    for (int i=2;i<=n;i++){
        if (check[i] == false) {
            prime[pn++] = i;
            for (int j=i*i;j<=n;j+=i) { // i*i는 n의 크기에 따라 i+i 또는 i*2로 바꾸는 것이 바람직하다.
            				// 그러나 n의 크기가 작다면 i*i가 더 빠름 
                                        // (i*i보다 작은 i의 배수들은 이미 i보다 작은 소수들의 배수에 의해 지워졌기 때문에 따로 처리할 필요가 없음)
                                        // i = 백만이면 int의 범위를 넘어가버리기 때문이다.
                check[j] = true;
            }
        }
    }
}

수를 실제 배열세어 실제로 지우려하면 시간이 오래 걸리므로 새로운 check 배열을 사용해서 제거 표시

O(NloglogN)의 시간이 걸리는 알고리즘

 

cf) 골드바흐의 추측

 - 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.

 - 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다. (위의 명제에 3을 더한 것)

아직 완전히 증명되지 않았다. (10의 18제곱 까지는 참이라고 증명이 되었다.)

 

4. 팩토리얼

팩토리얼은 매우 큰 값이다.

 

- 팩토리얼 0의 개수 구하기

N!에서 0의 개수를 구하는 문제

ex) 10! = 3620 -> 2개

이 이유는 10!을 소인수분해 해보면 알 수 있다. -> 0을 만들 수 있는 소인수는 10과 2*5밖에 없다. (각각 1개씩 있으므로 0은 총 2개)

5의 개수가 항상 2의 개수보다 적기 때문에 5의 개수만 세어주면 소수의 개수를 알아낼 수 있다.

(인수로 5가 들어가는 숫자 세어주기)

 -> 100을 기준으로

100/5 = 20 : 젓어도 5가 1개 들어가는 인수 20개 나옴

100/25 = 4 : 적어도 5가 2개 들어가는 인수 4개 나옴

따라서 100!의 0의 개수는 20+4 = 24로 24개이다.

import java.io.*;
import java.util.Stack;

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 len = Integer.parseInt(br.readLine());
        String cmd = br.readLine();
        Stack<Integer> stack = new Stack<>();
        String[] stringArray = cmd.split(" ");
        int[] array = new int[1000001];
        int[] NGF = new int[len];
        for (int i=0;i<len;i++) { // 등장횟수 세고 저장
            array[Integer.parseInt(stringArray[i])] += 1; // 정수의 초기값은 0이다.
        }
        /*
        stack에는 오등큰수가 정해지지 않은 수들의 위치가 들어간다.
        새로운 숫자의 입력이 들어오면 stack의 top부터 등장횟수의 대소비교를 진행한다.
        만약 새로운 숫자의 등장횟수가 크다면, stack에 담긴 숫자(왼쪽의 숫자)의 오큰수가 정해진 것이므로
        이를 stack에서 pop한다.
        새로운 숫자의 등장횟수가 더 작은 경우가 나올때까지 stack의 pop을 계속한다.
        새로운 숫자의 등장횟수가 더 작다면, stack의 top과 새로운 입력 모두 오등큰수가 없는 것이다.
        고로 새로운 숫자를 stack에 push한다.
        입력의 끝에 다다를 때까지 해당과정을 반복한다.
        위 과정에서 stack에 push되는 숫자들은 top으로 갈수록 수가 작아지는 내림차순으로 구성된다.
        (새로운 입력이 들어올 때마다 stack의 top과 등장횟수의 대소비교를 하고 등장횟수가 더 적은 경우에만 push하기 때문)
        (이렇게 stack이 구성되면 입력된 수열의 수가 top의 오등큰수가 되지 못하면 top 밑의 수들에 대해서도 오등큰수가 되지 않는다는 것을 알 수 있음)
         */
        stack.push(0); // 첫 입력은 다른 절차 없이 스택에 push (스택이 비어있기 때문 -> 찾을 오등큰수가 없음)

        for (int i=1;i<len;i++) { // 두번째 입력부터 반복문 처리
            int num = Integer.parseInt(stringArray[i]);
            if (stack.empty()) { // 스택이 비어있다면 다른 절차 없이 무조건 push
                stack.push(i);
                continue;
            }
            // 스택이 비어있지 않을 경우
            while (!stack.empty() && array[Integer.parseInt(stringArray[stack.peek()])] < array[num]) {
                // 입력된 수가 스택의 top의 오등큰수임
                NGF[stack.pop()] = num; // top을 pop하고 오등큰수를 할당
            }
            stack.push(i); // 입력된 수도 아직 오등큰수가 할당되지 않은 수임
        }

        while (!stack.empty()) { // 수열의 모든 수를 입력 받은 후에도 stack에 남이있는 수(오등큰수가 정해지지 않은 수)가 있다면
            NGF[stack.pop()] = -1; // 모두 pop하고 -1 할당해줌
        }

        for (int i=0;i<len;i++) {
            bw.write(NGF[i] + " ");
        }
        bw.flush();
        br.close();
        bw.close();
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/17299

 - byte : 0

 - short : 0

 - int : 0

 - long : 0

 - char : 0

 

 - float : 0.0

 - double : 0.0F

 

 - boolean : false

 

 - String, 배열 등 : null

지금까지 푼 문제중에서는 제일 헷갈렸다.. 

해설은 코드 내 주석 참고

import java.io.*;
import java.util.Stack;

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 len = Integer.parseInt(br.readLine());
        String cmd = br.readLine();
        Stack<Integer> stack = new Stack<>();
        String[] stringArray = cmd.split(" ");
        int[] NGE = new int[len];
        /*
        stack에는 오큰수가 정해지지 않은 수들의 위치가 들어간다.
        새로운 숫자의 입력이 들어오면 stack의 top부터 대소비교를 진행한다.
        만약 새로운 숫자의 입력이 크다면, stack에 담긴 숫자(왼쪽의 숫자)의 오큰수가 정해진 것이므로
        이를 stack에서 pop한다.
        새로운 숫자의 입력이 더 작은 경우가 나올때까지 stack의 pop을 계속한다.
        새로운 숫자의 입력이 더 작다면, stack의 top과 새로운 입력 모두 오큰수가 없는 것이다.
        고로 새로운 숫자를 stack에 push한다.
        입력의 끝에 다다를 때까지 해당과정을 반복한다.
        위 과정에서 stack에 push되는 숫자들은 top으로 갈수록 수가 작아지는 내림차순으로 구성된다.
        (새로운 입력이 들어올 때마다 stack의 top과 대소비교를 하고 입력이 작은 경우에만 push하기 때문)
        (이렇게 stack이 구성되면 입력된 수열의 수가 top의 오큰수가 되지 못하면 top 밑의 수들에 대해서도 오큰수가 되지 않는다는 것을 알 수 있음)
         */
        for (int i = 0; i < len; i++) {
            if (stack.empty()) { // stack이 비어있으면 해당 수에서 판별할 오큰수 없는 것이므로 입력수를 stack에 push해주고 다음 반복으로 넘어감
                stack.push(i);
                continue;
            }
            if (Integer.parseInt(stringArray[stack.peek()]) < Integer.parseInt(stringArray[i])) { // 입력으로 들어온 수열의 수가 top보다 크다면 -> stack의 top(오큰수가 정해지지 않은 수)에 대한 오큰수가 등장한 것이다.
                NGE[stack.pop()] = Integer.parseInt(stringArray[i]);
                while (!stack.empty()) { // top 밑의 수들(top보다 큰 수들)에 대해서도 오큰수가 될 수도 있기 때문에 입력수보다 큰 값이 나올때까지 pop하며 대소비교
                    if (Integer.parseInt(stringArray[stack.peek()]) < Integer.parseInt(stringArray[i])) { // 오큰수 성립
                        NGE[stack.pop()] = Integer.parseInt(stringArray[i]); // pop하고 그 아래 수들에 대해서도 대소비교
                    } else { // 오큰수 성립 안함 -> 그 밑의 수들에 대해서도 오큰수가 아니기 때문에 대소비교 중단
                        stack.push(i); // 입력으로 들어온 수도 오큰수가 정해진 수가 아니기 때문에 stack에 넣어주어야 함, 입력수보다 큰 수들은 while문을 통해 pop되었으므로 stack에 있는 수들 중 가장 작은 수가 되어 top이 될 수 있는 조건을 갖추므로 push한다.
                        break; // while문 탈출
                    }
                }
            }
            // 입력으로 들어온 수가 stack의 top보다 작음 -> 오큰수 성립 안함
            stack.push(i); // 입력된 수도 오큰수가 정해지지 않은 수이기 때문에 push (그리고 top보다 작은 수이기 때문에 push, 새로운 top이 됨)
        }
        while (!stack.empty()) { // 모든 입력이 처리된 뒤에도 오큰수가 정해지지 않은 수들에 대한 -1 할당 작업 필요
            NGE[stack.pop()] = -1;
        }
        for (int i = 0; i < len; i++) {
            bw.write(NGE[i] + " ");
        }
        bw.flush();
        br.close();
        bw.close();
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/17298