엘리스 알고리즘 코드 챌린지 Day2(07월 09일) - Java

Day2

나의 제출

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());
        int length = Integer.parseInt(st.nextToken());
        int count = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[length];
        for (int i=0; i<length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i=0; i<count; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int at = Integer.parseInt(st.nextToken());

            int[] temp = Arrays.copyOfRange(arr, start-1, end);
            Arrays.sort(temp);

            bw.write(String.valueOf(temp[at-1]));
            bw.newLine();
        }

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

 

알게된 내용

• 유클리드 호제법

// 최대공약수
public static int GCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

 

어떤 두 수 a와 b가 있고 a와 b를 나눈 나머지를 r이라 하였을 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

ex) a = 1071, b = 1029

1. 1071%1029 = 42

2. 1029%42 = 21

3. 42%21 = 0 이므로

1071과 1029의 최대공약수는 21

 

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

 

어떤 두 수의 곱은 두 수의 최소공배수와 최대공약수의 곱과 같다.

a * b = GCD(a, b) * LCM(a, b)

 

• 에라토스테네스의 체

boolean[] isPrime = new boolean[N];
Arrays.fill(isPrime, true); // true인 index는 소수
for (int i=2; i<=N; i++) {
    // 지우지 않은 수 찾음
    if (isPrime[i]) {
        // 찾은 수의 배수를 반복
        for (int j=i*2; i<=N; j+=i) {
            // j는 소수가 아니므로 false
            if (isPrime[j]) isPrime[j] = false;
        }
    }
}