2609: 최대공약수, 최소공배수

풀이

24 18

1. 둘중 작은 수를 택한다(18)
2. 작은수~1까지 반복하여 24를 나눈다.
   나눠지는 가장 첫번째수가 최대공약수 -> 6

최소공배수구하는 방법
-> 둘중 하나의 수 x 나머지수/최대공약수

-> 시간복잡도는 O(n), 공간복잡도는 O(1)안에 끝난다

import java.io.*;
public class Main{
    //최대공약수 구하는 함수
    public static int func(int n, int m){
        //입력 중 작은 값을 smaller라고 정의
        int smaller = n>m? m:n;
        //입력 중 큰 값을 bigger 정의
        int bigger = n==smaller? m:n;
        //smaller부터 시작해서 1까지 수를 하나씩 낮춰가며 센다.
        for(int i=smaller;i>1;i--){
            //둘다 나뉘어지는수가 있으면 그 수는 공약수일것이고, 큰수부터 count하기때문에
            // 가장 먼저 발견된 값이 최대공약수이다.
            if(smaller%i==0 && bigger%i==0){
                return i;
            }
        }
        // for문 조건에 아무것도 걸리지 않았다면 1을 리턴한다
        return 1;
    }
    public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String input[] = br.readLine().split(" ");
            int n = Integer.parseInt(input[0]);
            int m = Integer.parseInt(input[1]);
            // 최대공약수구하는 방법
            int gcd = func(n,m);
            System.out.println(gcd);
            // 최소공배수 = a * b / 최대공약수
            System.out.println(m*n/gcd);
    }
}

15649: N,M

풀이

• 순열을 만들어야한다. 백트래킹을 이용하여 순열을 만들어나가는 알고리즘을 사용하였다.
• 재귀함수로 문제를 구현하기 위해서는 종료조건이 필수적
• 문제를 누군가에게 설명을 잘하는것이 어렵다.
• 어떻게 풀기는 했지만 설명을 못하겠다. 제대로 이해하지 못했다

코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;

public class Main{
    public static void func(int n, int m, ArrayList<Integer> list){
        // 재귀함수의필수: 종료조건
        if(list.size() == m){
            list.forEach(e-> System.out.print(e+" "));
            System.out.println();
            //여기서 remove를 하게 되면 size == m일때만 remove를 하게 된다
            //나는 1234에서 4만 제거하면 안된다. 34를 제거하는 상황도있어야지 12에서 또다른 뒤의 숫자인 54를 붙일수가 있다
            return;
        }
        for(int i=1;i<=n;i++){
            if(!list.contains(i)){
                list.add(i);
                func(n,m,list);//재귀함수 호출 -> 무언가가 출력되고 나면(종료조건) 이 아래 명령문이 실행될 것이다.
                //출력이 되고 난 뒤에는 list의 요소를 제거하는 작업을 해주어야지 이전상황으로 완벽한 복귀가 가능하다
                list.remove(list.size()-1);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        ArrayList<Integer> list = new ArrayList<>();
        // 연속적인 숫자들을 가지고 순열만들기 -> 재귀함수
        // 숫자를 만들다가 다시 이전상황으로 돌아가서 또다른 숫자를 만든다 -> 백트래킹의 개념, 이 개념을 이용하면 재귀함수로 순열을 만드는것을 구현할 수 있게 됨

        func(n,m,list);

    }


}

두번 풀이

   public static void NM(int depth, int idx, String str){
        if(idx > n) return;
        if(depth==m) {
            System.out.println(str);
            return;
        }
        //계속해서 idx가 증가한다. 이 코드로는 오름차순으로 선택되는것만 가능하다
        NM(depth+1, idx+1, str+" "+ (idx+1));
        NM(depth, idx+1, str);
    }

세번 풀이

백트래킹이란 기본적으로 모든 경우의 수를 탐색하는 것이지만 특정 조건이 만족하는 경우에만 탐색을 하기 때문에 시간복잡도를 줄일 수 있게된다

시간복잡도: n!
1 2
1 3
1 4
2 1
2 3
2 4
를 잘 봐보면 선택된것은 제외한다음에 다음것이 나오는것을 확인할수있다
선택된것은 제외시키는 로직을 넣어주면된다

static int n;
    static int m;
    static boolean[] isPrinted;
    //n개의 숫자가 입력되면 그만둬야한다. 이를 판별할 depth라는 변수
    //idx는 앞으로 출력할 숫자를 의미한다
    //str은 넘긴 숫자를 출력할 문자열이다
    public static void NM(int depth, int idx, String str){
        //재귀함수는 기본적으로 종료조건이 필요하다
        if(idx > n) return;
        if(depth==m) {
            System.out.println(str);

            return;
        }
        //자기자신을 빼고 나머지를 모두 출력해야하니 for문을 사용
        //자기자신을 제외시켜야하니 boolean[]사용
        //자기를 사용하지 못하게 한다음에 그다음 반복문에서는 이전값을 사용할수있어야하니
        //false처리까지
        for(int i=1;i<=n;i++){
            //계속해서 idx가 증가한다. 이 코드로는 오름차순으로 선택되는것만 가능하다
            if(!isPrinted[i]){
                isPrinted[i] = true;
                //depth==0일때도 이대로 출력하면 앞에 공백생김
                if(depth!=0) NM(depth+1, i, str+" "+ i);
                else NM(depth+1, i, str+""+ i);
                isPrinted[i] = false;
            }

        }



    }

4948: 베르트공존 ''

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;

public class Main{
    //n이하의 수들중에서 소수의 개수를 return해주는 함수이다
    public static int sosu(int n){
        //1이하의 수들중에 소수의 개수는 0개다
        if(n==1) return 0;
        //2이하의 수들중에 소수의 개수는 2하나뿐이다
        if(n==2) return 1;
        //소수의 개수를 셀 변수 count 선언
        int count =0;
        //에라토스테네스의 체를 이용하기 위해. 소수인지아닌지를 판별하는 배열추가
        boolean isSosu[] = new boolean[n+1];
        //일단 모두 소수라고 가정
        for(int i=0;i<=n;i++){
            isSosu[i] = true;
        }
        //기본적으로 소수가 아닌수, 예외가 될법한 수들은 미리 세팅해둔다
        isSosu[0] = false;
        //0이나1을 false처리해주지 않는다면 모든 수가 false처리 된다
        isSosu[1] = false;
        //2를 true처리해주어야 한다.왜냐하면 아래 for문은 2부터 시작해서 isSosu(2) = true라는 전제하에 중첩for문을 도릭때문
        isSosu[2] = true;
        //2부터시작하여 제곱근n까지 돈다. 그 이유는 n = ab로 나타낼수있고, 적어도 둘중하나는 제곱근 n보다 작거나 같다.
        //그러니까 만약에 어떤 수가 소수가 아니라면 그 수는 ab로 나타낼수있을것이고, 그 ab둘중 하나는 제곱근n보다 무조건 작게 될것이다
        //제곱근n보다 작거나 같은수에 대해서는 해당수 a의 모든 배수에 대해서 검사를했기때문에
        //그 이상에 대해서는 검사해줄필요가없다
        for(int i=2;i<=Math.sqrt(n);i++){
            //소수가 아닌 수들은 그 수를 인수분해했을때의 수들, 즉, 더 작은수들에 의해 이미 큰수의 배수들은 false체크되었을 것이다
                if(isSosu[i]){
                    // 뽑혀진 수 i의 i*2,i*3.. 에 대해서 모두 소수아님 처리를 해준다
                    for(int j=i+i;j<=n;j+=i){
                        isSosu[j] = false;
                    }
            }

        }
        //소수의 개수를 count한다
        for(int i=1;i<=n;i++){
            if(isSosu[i]) count++;
        }
        return count;

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //일단 입력받는다
        int n = Integer.parseInt(br.readLine());
        //내가 입력한값이 0이 아닌 경우에만 계속해서 입력을 받는다
        while(n!=0){
            //2n이하의 수들중에서 소수개수를 뽑아서 a에 저장한다
            int a = sosu(2*n);
            //n이하의 수들 중에서 소수개수를 뽑아서 b에 저장한다
            int b = sosu(n);
            //일단 출력한다
            System.out.println(a-b);
            //출력한 뒤에 계속해서 입력을 받는다. 0이아니면 계속진행한다
            n = Integer.parseInt(br.readLine());

        }


    }


}

두번째 풀이

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;

public class Main{
    //똑같은 행위를 매번반복한다. 차라리 매번 메서드를 반복호출하는것보다
    //미리 결과를 내놓고 배열에서 참조만 하여 값을 return하는것이 성능상 유리할것이라고 생각하였다
    
    //소수여부를 기록할 변수
    static boolean isPrime[];
    //idx이하의 수들중에 소수인수들의 개수를 count하였다
    static int countPrime[];
    //2n은 123456*2만큼 올 수 있고 idx로 접근해야하기때문에 +1
    static final int MAX_SIZE = 123456*2+1;
    //소수를 구하는 메서드
    //소수를 구해서 isPrime에 소수면 true, 소수가 아니면 false라고 표시해줌
    public static void solve(){
        //기본적으로 소수라고 생각해준다음에 합성수들을 제거해나가는 방식을 사용
        for(int i=0;i<MAX_SIZE;i++){
            isPrime[i] = true;
        }
        //아래 중첩for문에 예외로 들어가는 값을을 처리해줌
        //0을 여러번 더하면 매번 false, 쓸데없이 반복문 많이돌음
        isPrime[0] = false;
        //1을 여러번더하면 모든수에 false
        isPrime[1] = false;
        //k=i+i여서 2의 반절은 1임 근데 1이 아래 for문을 안돌거니까 2도 예외처리해주어야함
        isPrime[2] = true;
        //MAXSIZE-1 = n을 의미함
        //MAXSIZE에 등호를 허락해주면 배열범위밖을 참조하게됨
        for(int i=2;i<=Math.abs(MAX_SIZE-1);i++){
            //소수가 아닌수의 배수들은 이미 진작에 체크가됏을것임
            if(isPrime[i]){
                //i의 배수들을 제거해준다
                for(int k=i+i;k<=MAX_SIZE-1;k+=i){
                    isPrime[k] = false;
                }
            }
        }

    }
    //isPrime배열을 활용해서 idx이하의 수들중에 소수의 개수르 체크해서 배열에 넣어줌
    public static int count(){
        int count =0;
        for(int i=1;i<isPrime.length;i++){
            if(isPrime[i]){
                count++;
            }
            //소수가 아닌 수에도 값을 넣어주어야함
            //아니면 소수인경우만 값을 넣어줘서 2n-n에서 제대로된 값이 안나옴
            //0이나와버림
            countPrime[i] = count;
        }
        return count;
    }
    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 n =1;
        isPrime = new boolean[MAX_SIZE];
        countPrime = new int[MAX_SIZE];
        solve();
        count();
        while(n!=0){
            n = Integer.parseInt(br.readLine());
            if(n==0) break;
            bw.write(countPrime[2*n] - countPrime[n]+"\n");

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


}