[BaekJoon-11727]-2xN 타일링 2

Posted on 2020-04-28 In Computer , CodingTest Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

2xn 타일링 2

문제

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

입력 2 -> 출력 3

입력 8 -> 출력 171

입력 12 -> 출력 2731

점화식

2xn 직사각형을 1x2, 2x2, 2x1 타일로 채우는 방법의 수

d[i] = 2x i직사각형을 채워야함

조건 1

2 x 1인 블록을 N 번재 위치에 놓으면

2 X (n-1) 만큼 나머지를 채워야함

조건 2

2 x 2 블록을 N 번째 위치에 놓으면

2 X (n-2) 만큼 나머지를 채워야함

조건 3

1 x 2 블록을 N 번째 위치에 놓으면

2 X (n-2) 만큼 나머지를 채워야함

그래서 점화식

Dp[N] = Dp[n-1] + (2 * Dp[N-2])

이된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine());
        out.write("" + tileOf2xn2(n));
        out.write("\n");
        out.flush();
        out.close();
        in.close();
    }
    public static int tileOf2xn2(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + (2*dp[i-2])) % 10007;
        }
        return dp[n];
    }
}

[BaekJoon-11726]-2xN 타일링

Posted on 2020-04-28 In Computer , CodingTest Disqus:
Symbols count in article: 907 Reading time ≈ 1 mins.

2xN 타일링

문제

2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다 ( 1<= n <= 1000)

출력

첫째 줄에 2xn 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 출력

점화식

조건 1 : N 번째 위치에 2x1타일이 들어가면

N번째 위치에 2x1 타일 한 개를 넣을 수 있으므로

Dp(N-1)

조건 2 : N 번째 위치에 1x2 타일이 들어가면

끝에 1x2 를 두개 넣을 수 있으므로

Dp(N-2)

Dp(N) = Dp[N-1] + Dp[N-2]

소스코드


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine());
        out.write("" + tileOf2xn(n));
        out.write("\n");
        out.flush();
        out.close();
        in.close();
    }
    public static int tileOf2xn(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }
        return dp[n];
    }
}

[BaekJoon-1463] 1로 만들기

Posted on 2020-04-28 Edited on 2020-06-09 In Computer , CodingTest Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

해결

Table[i] = i 로 만드는데 최소 횟수

i가 3으로 나누어 떨어질경우 : Table[i / 3] + 1
i가 2으로 나누어 떨어질경우 : Table[i / 2] + 1
i가 1을 뺄 경우 : Table[i - 1] + 1

최솟값을 구하는 것으로

table[i] = Min(Table[i/3], Table[i/2], Table[i-1])+1

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine());
        out.write("" + makeItOne(n));
        out.write("\n");
        out.flush();
        out.close();
        in.close();
    }
    public static int makeItOne(int n) {
        int[] table = new int[n + 1];
        table[1] = 0;
        for (int i = 2; i <= n; i++) {
            table[i] = table[i - 1] + 1;
            if (i % 2 == 0 && table[i] > table[i / 2] + 1) {
                table[i] = table[n / 2] + 1;
            } else if (i % 3 == 0 && table[i] > table[i / 3] + 1) {
                table[i] = table[n / 3] + 1;
            }
        }
        return table[n];
    }
    //짧은 코드
    public static int makeItOne2(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i / 2] + (i % 2), dp[i / 3] + (i % 3)) + 1;
        }
        return dp[n];
    }
}

5. 다이나믹 프로그래밍(Dynamic Programming)

Posted on 2020-04-28 In Computer , Algorithm Disqus:
Symbols count in article: 2.7k Reading time ≈ 2 mins.

Dynamic Programming(동적계획법)

풀고자하는 문제가 여러단계의 반복되는 부분문제로 이루어졌을 때 각 단계 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법
문제를 부분 문제로 단계적으로 나누고, 가장 작은 부분 문제의 답부터 구해 올라오면서 전체 문제의 해를 구하는 것. 즉, 큰 문제를 작은문제로 나눠서 푸는 것
계획법(Programming)이란 용어는 코딩(cooding)이 아니라 테이블을 채운다는 문자적 의미(선형 계획법과 유사)

동적계획법 전략

동적 계획법과 메모하기는 함께 동작
메모하기(이미 푼부속문제들의 테이블)를 이용하는 방법으로 많은 문제에서 지수적 복잡도를 다항적 복잡도로 감소시킬 수 있다.

주요 요소

재귀 : 부속 문제들을 재귀적으로 푼다.
메모하기 : 이미 계산된 값들을 테이블에 저장(메모하기는 Cashing(캐싱)을 뜻함)
동적계획법 = 재귀 + 메모하기

분할정복과 동적계획법 차이

분할정복	동적계획법
분할정복은 위에서 아래로 쪼갬(Top-down)	제일 작은 부분 문제부터 상위에 있는 문제로 풀어올라감(Bottom Up)
분할 정복으로 쪼갠 각 부분 문제는 완전히 새로운 하나의 문제로 다룸(부분문제들이 독립적)	문제의 각 단계에 있는 부분 문제들은 그 이전 단계에 있는 문제들의 답에 의존(부속 문제들이 겹침)
한번 푼적이 있는 부분문제의 답은 다시 품	한번 푼적이 있는 부분문제의 답은 다시푸는 일이 없도록 테이블등에 저장

전략속성

최적 부속 구조(Optimal Substructure): 문제의 정답을 작은 문제의 정답에서 구할 수 있다. ex) 서울에서 부산까지 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야한다.

겹치는 부속 문제(Overlapping Subproblems) : 여러 번 반복되는 몇 가지 부속문제들을 포함하는 재귀적 해법.

-    큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
-    문제를 작은 문제로 쪼갤 수 있다.

동작 방식

문제를 부분문제로 나눔
가장 작은 부분문제로부터 해를 구한 뒤 테이블에 저장
테이블에 저장되어 있는 부분문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.

동적 계획법으로 설계된 피보니치 수

public static long fibonacci2(int n) {
  long result = 0;
  long[] table = new long[n + 1];
  if (n == 0 || n == 1) {
    return n;
  }
  table[0] = 0;
  table[1] = 1;
  for (int i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  result = table[n];
  return result;
}

최장 공통 부분 순서(Longer Common SubSequence : LCS)

두 수열의 가장 긴 공통 부분 수열을 찾아내는 문제.
1. X, Y 두 수열 마지막이 공통 부분 수열인 경우
  - LCS(Xi-1, Yj-1) + 1, Xi = Yj
  - X와 Y의 문자가 같다(X[i] == Y[j])
  - X와 Y의 LCS의 길이는 마지막 문자를 하나 줄인 수열 X와 마지막을 하나 줄인 수열 Y간의 LCS에 공통 문자의 길이 1을 추가한 것과 같다.
  - 일반화 하면, 마지막 index가 각각 i, j일 경우 X[i] == Y[j]이면 LCS[i][j] = LCS[i-1][j-1] + 1이다.
2. 수열 X 마지막이 공통 부분 수열에 속하지 않는 경우
  - LCS(Xi-1,Yj) > LCS(Xi, Yj-1)
  - X와 Y의 문자가 다르다(X[i] != Y[j])
  - X와 Y의 LCS는 마지막 문자를 하나 줄인 수열 X와 수열 Y간의 LCS와 동일하다.
  - 일반화 : LCS[i][j] = LCS[i-1][j]이다.
3. 수열 Y 마지막이 공통 부분 수열에 속하지 않는 경우
  - LCS(Xi-1, Yj) < LCS(Xi,Yj-1)
  - X와 Y의 문자가 다르다(X[i] != Y[j])
  - X와 Y의 LCS는 수열 X와 마지막 문자를 하나 줄인 수열 Y간의 LCS와 동일하다.
  - 일반화 : LCS[i][j] = LCS[i][j-1]이다.

해결방법

문제를 부분문제로 나눈다.
가장 작은 부분문제부터 해를 구하고 뒤 테이블에 저장
테이블에 저장되어 있는 부분문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.

public static int LCS(String X, String Y, int[][] table) {
  for (int i = 0; i < X.length(); i++) {
    table[i][0] = 0;
  }
  for (int j = 0; j < Y.length(); j++) {
    table[0][j] = 0;
  }

  for (int i = 1; i <= X.length(); i++) {
    for (int j = 1; j <= Y.length(); j++) {
      if (X.charAt(i-1) == Y.charAt(j-1)) {
          table[i][j] = table[i-1][j-1] + 1;
      } else {
          table[i][j] = table[i-1][j] >  table[i][j-1] ? table[i-1][j] : table[i][j-1];
      }
    }
  }
  return table[X.length()-1][Y.length()-1];
}

public static void LCS_TraceBack(String x, String y,int i, int j,  int[][] table, String lcs) {
  if (i == 0  || j == 0) return;

  if (table[i][j] > table[i][j-1] && table[i][j] > table[i-1][j] && table[i][j] > table[i-1][j-1]) {
    String tmp = lcs;
    lcs = String.format("%c%s ", x.charAt(i-1), tmp);
    System.out.println(lcs);
    LCS_TraceBack(x,y, i-1 ,j-1, table, lcs);
  } else if (table[i][j] > table[i-1][j] && table[i][j] == table[i][j-1]) {
    LCS_TraceBack(x,y,i, j-1, table, lcs);
  } else {
    LCS_TraceBack(x,y, i-1, j, table, lcs);
  }
}

[BaekJoon-17087] 숨바꼭질 6

Posted on 2020-04-02 In Computer , CodingTest Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

[BaekJoon-17087] 숨바꼭질 6

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, …, AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

출력

가능한 D값의 최댓값을 출력한다.

예제 입력 1

1 2	3 3 1 7 11

예제 출력 1

예제 입력 2

1 2	3 81 33 105 57

예제 출력 2

예제 입력 3

1 2	1 1 1000000000

예제 출력 3

999999999

해결

수빈이는 S 동생은 $A_1 … A_N$ 에 있다고 하면 수빈이는 x-> X+D나 X - D 로 이동할 수 있다고 하고, D의 최댓값을 구하는 문제

A 에서 B 로 이동 하는 경우(A < B) : X -> X + D나 X - D 로만 이동하려면 B - X가 D의 배수가 되어야 한다.

A 에서 B C 로 이동하는 경우(A < B, A < C) : X-> X + D나 X - D로만 이동하려면 D-X가 D의 배수가 되어야하고, C-X가 의 배수가 되어야한다.

예를들어 시작점 S 가 2이고 도착지가 26이면 둘 사이 차이나는 거리 D = 24 이다.

그래서 여기서 공통된 약수의 합을 구하면 되므로

$|A_1 - X|,|A_2 - X|,|A_3 - X|…|A_n - X|$ 의 최대공약수를 구하면된다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        g2();
    }

    public static void g2() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        String[] split = str.split(" ");
        int n = Integer.parseInt(split[0]);
        int s = Integer.parseInt(split[1]);

        String str2 = in.readLine();
        String[] split2 = str2.split(" ");
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(split2[i]);
            a[i] = Math.abs(x-s);
        }

        int result = a[0];
        for (int i = 1; i < n; i++) {
            result = gcd(result, a[i]);
        }

        out.write(result + "\n");
        out.flush();;
        out.close();
        in.close();
    }

    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

[BaekJoon-9613] GCD 합

Posted on 2020-04-02 Edited on 2020-05-01 In Computer , CodingTest Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

[BaekJoon-9613] GCD 합

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

예제 입력 1

3
4 10 20 30 40
3 7 5 12
3 125 15 25

예제 출력 1

1
2
3

70
3
35

해결

최대공약수는 유클리드 호재법을 이용했다.
여기서 최대공약수의 합이라고 되어있는데 가능한 모든 쌍이라는 것이

10 20 30 40

이 있다면
10, 20, 30, 40 의 최대굉약수 합

20, 30, 40 의 최대공약수 합

30, 40 의 최대공약수 합

이 된다.

그래서 루프를 두 번 돌려야하며 i 는 i to n - 1번 만큼 루프를 (왜냐하면 마지막 값은 하나 뿐이니..)
j 는 i + 1 to n번 만큼 루프를 돌린다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        sumOfGCD();
    }

    public static void sumOfGCD() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());

        while (t-- != 0) {
            String s = in.readLine();
            String[] split = s.split(" ");
            int n = Integer.parseInt(split[0]);
            long sum = 0;
            for (int i = 1; i <= n - 1; i++) {
                for (int j = i + 1; j <= n; j++) {
                    sum += gcd(Integer.parseInt(split[i]), Integer.parseInt(split[j]));
                }
            }
            out.write(sum + "\n");
            out.flush();
        }
        out.close();
        in.close();
    }

    public static long gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

문제 사이트 : https://www.acmicpc.net/problem/9613

[BaekJoon-6588] 골드바흐의 추측

Posted on 2020-04-01 Edited on 2020-04-02 In Computer , CodingTest Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

[BaekJoon-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

예제 출력 1

1
2
3

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

풀이방법

에라토스테네스의 체를 가지고 소수 배열을 만들어놓고 소수배열이면서 n-1번 째 배열이 소수이면 두 소수의 합을 구할 수 있다.

에라토스테네스의 체에서 소수가 아닌 것은 true 고 소수는 false로 되어 있다.

i 번째 소수 eq i 번째 소수 eq (n - i) 번째 소수

즉
if (!check[i] && (!check[i] && !check[n - i]))

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        goldbachsConjecture();
    }

    public static void goldbachsConjecture() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int length = 1000000;
        boolean[] check = new boolean[length + 1];
        check[0] = check[1] = true;
        for (int i = 2; i <= length; i++) {
            if (!check[i])
                for (int j = i + i; j <= length; j += i) check[j] = true;
        }

        int n = 0;
        int a;
        boolean flags;
        while ((n = Integer.parseInt(in.readLine())) != 0) {
            a = 2;
            flags = false;
            for (int i = a; i < n; i++) {
                if (!check[i] && (!check[i] && !check[n - i])) {
                    out.write(n + " = " + i + " + " + (n - i) + "\n");
                    flags = true;
                    break;
                }
            }
            if (!flags) out.write("Goldbach's conjecture is wrong.");
            out.flush();
        }


        out.close();
        in.close();
    }
}

문제 사이트 : https://www.acmicpc.net/problem/6588

[BaekJoon-1929] 소수구하기

Posted on 2020-04-01 In Computer , CodingTest Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

[BaekJoon-1929] 소수구하기

문제

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

출력

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

예제 입력 1

3 16

예제 출력 1

풀이

일반 소수구하기로 하면 시간초과난다.

그래서 에라토스테네스의 체를 이용하여 문제를 해결할 수 있다.

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 ‘에라토스테네스의 체’라고 부른다. 따지고 보면 $f(x)=x1_P(x)$ 의 수열 중 0이 아닌 것을 표로 시각화한 것이라고 볼 수 있다. 참조 : 나무위키

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {

        prime();
    }

    public static void prime() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        String[] split = str.split(" ");
        int m = Integer.parseInt(split[0]);
        int n = Integer.parseInt(split[1]);

        int[] num = new int[n + 1];
        boolean[] check = new boolean[n + 1];
        for (int i = 0; i <= n; i++) {
            num[i] = i;
        }
        check[0] = check[1] = true;
        for (int i = 2; i <=n; i++) {
            if (!check[i])
                for (int j = i + i; j <= n; j+=i) check[j] = true;
        }

        for (int i = m; i <=n; i++) {
            if (!check[i])
                out.write(num[i] + "\n");
        }
        out.flush();
        out.close();
        in.close();
    }
}

문제 사이트 : https://www.acmicpc.net/problem/6588

[BaekJoon-2609] 최대공약수와 최소공배수

Posted on 2020-03-31 Edited on 2020-04-01 In Computer , CodingTest Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

[BaekJoon-2609] 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

1
2

6
72

풀이

최대공약수 : gcd(a, a%b) 유클리드 호재법을 통해 최대공약수를 구할 수 있다.

호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘.

a 를 b로 나눈 나머지를 r 이라고 했을 때 GCD(a,b) = GCD(b,r)과 같다.
여기서 r이 0 이면 b가 최대공약수가 된다.

$GCD(24,16)=GCD(16,8)=GCD(8,0)=8,13$

최소공배수 : $L = lcm(a, b)$ 은 $L= lcm(a, b)= a * b / gcd(a, b)$이 성립

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        String[] split = str.split(" ");
        int a = Integer.parseInt(split[0]);
        int b = Integer.parseInt(split[1]);
        int gcd = gcd(a, b);
        out.write(gcd + "\n");
        out.write(lcm(a, b, gcd) + "\n");
        out.flush();
        out.close();
        ;
        in.close();
        ;
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    //재귀를 이용한 gcd
    public static long gcd2(long a, long b) {
		return b != 0 ? gcd(b, a % b) : a;
	}

    public static int lcm(int a, int b, int gcd) {
        return (a * b) / gcd;
    }
}

문제 사이트 : https://www.acmicpc.net/problem/6588

[BaekJoon-11656] 접미사 배열

Posted on 2020-03-30 In Computer , CodingTest Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

[BaekJoon-11656] 접미사배열

문제

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

출력

첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

예제 입력 1

baekjoon

예제 출력 1

aekjoon
baekjoon
ekjoon
joon
kjoon
n
on
oon

해결방버

자바 문자열 함수 중 substring() 을 이용하면 문자열을 분리하고 sort() 를 통해 정렬한다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws Exception {
        suffixOfArray();
    }

    public static void suffixOfArray() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        String[] arr = new String[str.length()];

        for (int i = 0; i<str.length(); i++) {
            arr[i] = str.substring(i);
        }
        Arrays.sort(arr);
        for (String s : arr) {
            out.write(s+'\n');
        }
        out.flush();
        out.close();;
        in.close();
    }
}

문제 사이트 : https://www.acmicpc.net/problem/11656