더 이상 물러설 곳이 없다

www.acmicpc.net/problem/2004

문제

(nm)의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

출력

첫째 줄에 (nm)의 끝자리 0의 개수를 출력한다.

예제 입력 1

25 12

예제 출력 1

2

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // nCm = n! / (m! * (n-m)!)
        // m!, (n-m)!은 분모에 들어가기 때문에 역으로 뺴줘야 한다

        int cntOfTwo = 0, cntOfFive = 0;
        for(long i = 2; i <= n; i*=2) cntOfTwo += n / i;
        for(long i = 2; i <= m; i*=2) cntOfTwo -= m / i;
        for(long i = 2; i <= n-m; i*=2) cntOfTwo -= (n-m) / i;

        for(long i = 5; i <= n; i*=5) cntOfFive += n / i;
        for(long i = 5; i <= m; i*=5) cntOfFive -= m / i;
        for(long i = 5; i <= n-m; i*=5) cntOfFive -= (n-m) / i;

        int ans = Math.min(cntOfTwo, cntOfFive);
        System.out.println(ans);
    }
}

codeung.tistory.com/170 와 유사한 문제이다.

다만 이 문제에서는 5의 개수로 (2 * 5) 쌍의 개수를 퉁칠 수 없다.

nCm = n! / (m! * (n-m)!) 인데, n!을 m! * (n-m)! 으로 나눌 때 변수가 생길 수 있기 때문에 온전히 nCm 안에 있는 (2 * 5) 쌍의 개수를 전부 구해야 한다.

(분모에 위치한 m!, (n-m)! 에 대해서는 나온만큼 n!에서 나온 개수에서 빼주면 된다.)

주의할 점은 각 반복의 변수 i 를 int가 아닌 long으로 써야 한다는 것이다.

n, m의 상한은 20억으로 int의 범위 안에서 충분히 처리가 가능하긴 하지만.. 반복변수 i는 1씩 증가하는 것이 아니라 2배, 5배씩 증가하기 때문에 n과 int 범위 안에서 잘 있다가 갑자기 int 범위를 벗어나게 될 수 있기 때문이다.

실제로 int i 를 사용할 경우 0 divide exception이 발생하게 된다.

www.acmicpc.net/problem/1676

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

예제 입력 1 복사

10

예제 출력 1 복사

2

예제 입력 2 복사

3

예제 출력 2 복사

0

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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 cntOfFive = 0;
        cntOfFive += n / 5;
        cntOfFive += n / 25;
        cntOfFive += n / 125;

        System.out.println(cntOfFive);
    }
}

n을 소인수분해 했을 때 10이 즉, 뒤에 0이 붙을 수 있는 경우는 (2 * 5) 쌍이 나올 때 뿐이다.

즉, n을 소인수분해 하여 (2*5) 꼴이 몇 개 나오는지를 알아내면 된다.

그런데 2는 짝수가 나올 때마다 하나씩 추가되기 때문에 무조건 5보다 많이 나올 수밖에 없다.

따라서 n 안에 5의 배수가 몇 번이나 들어있는지를 구하면 그게 곧 (2 * 5) 쌍의 개수이다.

여기서 주의할 점은, 25, 125 등의 수는 5의 배수가 맞긴 하지만 5가 하나만 들어있는 게 아니다

(25 = 5 * 5, 125 = 5 * 5 * 5 ... )

즉, 5의 배수의 개수를 구한 다음 25의 배수의 개수를 구해서 25 = 5 * 5 에서 남아있는 5를 한 번 더 세어줘야 한다.

(125는 5 * 5* 5 이므로 5가 한 번 더 들어가니깍 125의 배수의 개수도 구해야 한다.)

n의 제한범위 500 안에서 5의 지수승 꼴은 최대 5^3 = 125 까지만 등장하기 때문에 125의 배수의 개수까지만 구해주면 된다.

www.acmicpc.net/problem/10872

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)가 주어진다.

출력

첫째 줄에 N!을 출력한다.

예제 입력 1 복사

10

예제 출력 1 복사

3628800

예제 입력 2 복사

0

예제 출력 2 복사

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());
        int factorial = 1;
        for(int i = 1; i <= n; i++) {
            factorial *= i;
        }
        System.out.println(factorial);
    }
}

www.acmicpc.net/problem/11653

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

예제 입력 1

72

예제 출력 1

2

2

2

3

3

예제 입력 2

3

예제 출력 2

3

예제 입력 3

6

예제 출력 3

2

3

예제 입력 4

2

예제 출력 4

2

예제 입력 5

9991

예제 출력 5

97

103

풀이 .

import java.io.*;

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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        if(n == 1) return;
        while(n != 1) {
            for(int i = 2; i <= n; i++) {
                if(n % i == 0) {
                    n /= i;
                    sb.append(i + "\n");
                    break;
                }
            }
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

그냥 소인수분해 하면 된다.

singleton, prototype 처럼 @Scope를 통해 request 객체를 지정해줄 수 있다.

request 객체는 Http 요청이 발생하면 생성되는 객체이다.

각 요청마다 하나씩 생성되기 때문에 수많은 요청이 들어와도 request 객체를 통해 전부 구분할 수 있다.

하지만 코드를 짤 때 아무런 조치도 취하지 않고 @Scope(value = "request") 처리만 해놓으면 서버가 제대로 동작하지 않는다.

말했듯이 request 객체는 Http 요청이 발생할 때 생성되는 객체인데 서버를 막 띄운 상태에서는 어떠한 Http 요청도 들어오지 않은 상태이기 때문이다.

즉, 생성된 request 객체는 없는데 request 객체에 의존성을 가진 Controller, Service 등의 클래스들이 컴포넌트 스캔의 대상이 되어 DI를 실행할 때 문제가 생기는 것이다.

이를 두 가지 방식으로 해결할 수 있다.

1. ObjectProvider<T>

request 객체에 의존성을 띈 모든 코드에 request 객체 대신 ObjectProvider를 두고 request 객체 사용 로직에서는 provider.getObject() 로 객체를 받아서 사용하는 것이다.

2. Proxy (이걸 더 많이 사용하는 듯)

@Scope(value = "request", proxyMode = ScopedProxyMode.TARGET_CLASS)

(타겟의 형태에 따라서 TARGET_CLASS or INTERFACES 선택)

이렇게 하면 Http 요청 발생 여부와 관계 없이 request 클래스를 상속받은 가짜 프록시 클래스의 객체를(CGLIB) 생성하여 request 객체에 의존성을 가진 다른 빈에 대해서 DI를 실시한다.

request 객체를 사용하는 로직에서는 호출 시점에 진짜 request 객체를 찾아서 사용한다.

(진짜 request 객체를 찾아내는 로직은 가짜 프록시 객체 내부에서 진행된다.)

Proxy를 사용하면 어노테이션 설정 변경만으로 request 객체를 마치 싱글톤 객체를 사용하는 것처럼 사용할 수 있다.

(하지만 진짜 reqeust 객체는 Http 요청마다 생성되는 것이기 때문에 실제로는 여러 개가 존재)

@Scope의 무분별한 사용을 경계해야 한다.

유지보수에 큰 장애가 될 수 있으니 꼭 필요한 곳에서만 사용하자

@Scope를 통해 빈의 스코프를 지정해줄 수 있다.

(디폴트는 싱글톤 빈이다.)

프로토타입.

@Scope("prototype") 으로 지정해준다.

싱글톤처럼 하나의 객체를 계속 사용하는 방식이 아닌 호출때마다 매번 객체를 생성한다.

@PostConstruct 메서드는 스프링이 실행해주지만 그 이후의 관리는 전적으로 사용자의 몫으로 남겨진다.

그래서 @PreDestroy 메서드는 사용자가 명시적으로 호출해줘야 한다.

싱글톤과 프로토타입을 함께 사용하면 문제가 발생할 수 있다.

싱글톤에서 프로토타입에 대한 의존성을 갖고 있을 경우.

싱글톤 객체는 한 번만 생성되고 그 이후부터는 쭉 스프링 컨테이너에 저장되어있을뿐 새로 만들어지지 않는다.

당연히 그 안에 있는 프로토타입 빈도 의존성 주입 당시에 한 번만 생성되어 그대로 해당 객체가 유지된다. 

이는 접근할 때마다 새로운 객체를 생성한다는 프로토타입의 원래 목적에 반하는 동작이다.

(여러 종류의 싱글톤에서 한 프로토타입을 의존할 경우에는 각각 다른 프로토타입 빈이 싱글톤에 등록된다. 그 이후로 쭉 유지되는건 똑같지만)

이러한 문제점을 ObjectProvider<T>를 사용하여 해결할 수 있다.

private ObjectProvider<PrototypeBean> prototypeBeanProvider;
PrototypeBean prototypeBean = prototypeBeanProvider.getObject();

기존 방식처럼 생성자를 통해 DI를 실행하면 프로토타입이 프로토타입일 수 없는 문제가 발생했다.

ObjectProvider를 사용하여 해당 프로토타입 빈에 대한 프로바이더를 만들 수 있고, 이를 통해 getObject()로 프로토타입 빈에 접근한다.

이때, 미리 만들어져있는 빈을 제공하는 것이 아니라 getObject() 가 호출될 때 새 프로토타입 빈을 생성하여 반환해준다.

(getObject() 하려는 빈이 프로토타입 빈일 때만임. 사실 Provider는 프로토타입을 위한 기능이 아니라 DL을 위한 기능임)

즉, 호출할 때마다 매번 생성된다. 프로토타입으로서의 올바른 동작법이다. 이를 DL (Dependency Lookup) 이라고 한다.

(물론 ObjectProvider에 대한 DI는 따로 해줘야 한다.)

사실 프로토타입을 사용하는 일은 거의 없고 대부분이 싱글톤으로 해결된다고 한다.

www.acmicpc.net/problem/6588

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

예제 입력 1

8

20

42

0

예제 출력 1

8 = 3 + 5

20 = 3 + 17

42 = 5 + 37

풀이 .

import java.io.*;

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));
        StringBuilder sb = new StringBuilder();

        // get prime (sieve of eratosthenes)
        int[] prime = new int[1000001];
        boolean[] isNotPrime = new boolean[1000001];
        int cntOfPrime = 0;
        for(int i = 2; i <= 1000000; i++) {
            if(isNotPrime[i] == false) {
                prime[cntOfPrime++] = i;
                for(int j = i + i; j <= 1000000; j+=i) {
                    isNotPrime[j] = true;
                }
            }
        }

        String input = null;
        while(!(input = br.readLine()).equals("0")) {
            int n = Integer.parseInt(input);
            for(int i = 1; i <= cntOfPrime; i++) {
                if(isNotPrime[n - prime[i]] == false) {
                    sb.append(n + " = " + prime[i] + " + " + (n - prime[i]) + "\n");
                    break;
                }
            }
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

1. 에라토스테네스의 체를 사용해 MAX 범위 내의 소수들의 배열을 미리 구해놓는다.

2. n - prime[i]이 소수인지를 작은 소수부터 비교한다.

3. b - a가 최대인 a, b 라는 조건을 맞추기 위해 2번에서 작은 소수부터 검사한 것. 정답 찾으면 바로 break하여 다음 테스트 케이스 수행

(골드바흐의 추측은 10^18 이하까지는 참인 것이 증명되었으므로 실패 경우에 대한 고려는 하지 않는다.)

www.acmicpc.net/problem/1929

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3

5

7

11

13

풀이 .

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static boolean isPrime(int num) {
        if(num == 2) return true;
        if(num == 0 || num == 1 || num % 2 == 0) return false;
        for(int i = 3; i <= Math.sqrt(num); i+=2) {
            if(num % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        for(int i = m; i <= n; i++) {
            if(isPrime(i)) sb.append(i + "\n");
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}