'Computer/Algorithm_Java' 카테고리의 글 목록 (5 Page)

Computer/Algorithm_Java

[Algorithm_Java] 10872번 팩토리얼 (Success) 2023.10.01
[BaekJoon] 11866번 요세푸스 문제 0 문제 풀이 (Success) 2023.09.30
[BaekJoon] 1934번 최소공배수 문제 풀이 (Success) 2023.09.29
[BaekJoon] 11478번 서로 다른 부분 문자열의 개수 문제 풀이 (Success) 2023.09.28
[BaekJoon] 15651번 N과 M (3) 문제 풀이 (Success) 2023.09.26

PREV 이전 1 2 3 4 5 6 7 8 ···35 NEXT 다음

[Algorithm_Java] 10872번 팩토리얼 (Success)

HJ0216 2023. 10. 1.

2023. 10. 1.

10872번: 팩토리얼

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

www.acmicpc.net

☕ Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int cnt = Integer.parseInt(br.readLine());
 
       int result = 1;
        for(int i = 1; i<=cnt; i++) {
            result *= i;
        }
 
        bw.write(result+"");
        
        bw.flush();
        bw.close();
 
    }
 
}
 
 

1. result *= i;

- 입력값만큼 팩토리얼 계산

😮 이 외의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    public static void main(String[] args) throws IOException {
 
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        bw.write(factorial(N) + "");
 
        bw.flush();
        bw.close();
    }
 
    public static int factorial(int N) {
        if (N <= 1)
            return 1;
        return N * factorial(N - 1);
    }
 
}
 
 

1. return N * factorial(N - 1);

- 재귀호출 사용

🚨 값의 입력범위가 0부터 가능하므로 N을 1보다 작거나 같은 범위로 지정

- N==1로 지정할 경우, N==0일 때 StackOverFlow 발생

🔗 소스 코드
GitHub

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[Algorithm_Java] 15652번 N과 M (4) (Success) (1)	2023.10.05
[Algorithm_Java] 24479번 알고리즘 수업 - 깊이 우선 탐색 1 (Success) (0)	2023.10.02
[BaekJoon] 11866번 요세푸스 문제 0 문제 풀이 (Success) (0)	2023.09.30
[BaekJoon] 1934번 최소공배수 문제 풀이 (Success) (0)	2023.09.29
[BaekJoon] 11478번 서로 다른 부분 문자열의 개수 문제 풀이 (Success) (0)	2023.09.28

[BaekJoon] 11866번 요세푸스 문제 0 문제 풀이 (Success)

HJ0216 2023. 9. 30.

2023. 9. 30.

11866번: 요세푸스 문제 0

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

www.acmicpc.net

☕ Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        List<Integer> list = new ArrayList<>();
 
        for (int i = 0; i < N; i++) {
            list.add(i + 1);
        }
 
        StringBuffer sb = new StringBuffer();
 
        int idx = 0;
        for (int i = 0; i < N; i++) {
            idx = idx + K - 1 > list.size() ? idx + K - 1 - list.size() : idx + K - 1;
            while (idx >= list.size()) {
                idx = idx - list.size();
            }
            sb.append(list.get(idx));
            if (i != (N - 1)) {
                sb.append(", ");
            }
            list.remove(idx);
        }
 
        bw.write("<" + sb + ">");
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

1. idx = idx - list.size();

- idx가 list size보다 크지 않도록 반복문 진행

😮 이 외의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        Queue<Integer> queue = new LinkedList<>();
 
        for (int i = 0; i < N; i++) {
            queue.add(i + 1);
        }
 
        StringBuilder sb = new StringBuilder("<");
 
        while (queue.size() > 1) {
            for (int i = 0; i < K - 1; i++) {
                queue.add(queue.poll());
            }
            sb.append(queue.poll() + ", ");
        }
 
        sb.append(queue.poll() + ">");
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

1. queue.add(queue.poll());

- K값 전까지 모든 숫자를 제거하고 뒤로 이동

2. sb.append(queue.poll() + ", ");

- K값 제거

🔗 소스 코드
GitHub

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[Algorithm_Java] 24479번 알고리즘 수업 - 깊이 우선 탐색 1 (Success) (0)	2023.10.02
[Algorithm_Java] 10872번 팩토리얼 (Success) (0)	2023.10.01
[BaekJoon] 1934번 최소공배수 문제 풀이 (Success) (0)	2023.09.29
[BaekJoon] 11478번 서로 다른 부분 문자열의 개수 문제 풀이 (Success) (0)	2023.09.28
[BaekJoon] 15651번 N과 M (3) 문제 풀이 (Success) (0)	2023.09.26

[BaekJoon] 1934번 최소공배수 문제 풀이 (Success)

HJ0216 2023. 9. 29.

2023. 9. 29.

1934번: 최소공배수

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있

www.acmicpc.net

☕Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
 
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            int max = 0;
            
            for(int j=1; j<=45000; j++) {
                if(a % j ==0 && b % j == 0) {
                    max = Math.max(max, j);
                }
            }
 
            long result = (a/max) * (b/max) * max;
 
            bw.write(result+"\n");
        }
        
        
        bw.flush();
    }
}
 
 

🤔 해설

1. for(int j=1; j<=45000; j++)

- 최대값 45,000

2. if(a % j ==0 && b % j == 0)

- 공약수 탐색

3. max = Math.max(max, j);

- 최대공약수 탐색

4. long result = (a/max) * (b/max) * max;

- 최소공배수 공식

- 자료값 타입 유의

😮 이 외의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
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 N = Integer.parseInt(br.readLine());
 
        StringTokenizer st;
 
        StringBuilder sb = new StringBuilder();
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
 
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            sb.append(lcm(a, b)).append('\n');
        }
 
        br.close();
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
    // 최대공약수 재귀 방식
    public static int gcd(int a, int b) {
        if (b == 0)
            return a;
 
        return gcd(b, a % b);
    }
 
    // 최소공배수 : Least Common mulitple
    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}
 
 

유클리드 호제법 - 재귀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
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 N = Integer.parseInt(br.readLine());
 
        StringTokenizer st;
 
        StringBuilder sb = new StringBuilder();
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
 
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            sb.append(lcm(a, b)).append('\n');
        }
 
        br.close();
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
    // 최대공약수 반복문 방식
    public static int gcd(int a, int b) {
        
        while(b!=0) {
            int r = a % b;
            a = b;
            b = r;
        }
 
        return a;
    }
 
    // 최소공배수 : Least Common Mulitiple
    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}
 
 

유클리드 호제법 - 반복문

🔗 소스 코드
GitHub

📚 참고 자료

[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]

www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 알

st-lab.tistory.com

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[Algorithm_Java] 10872번 팩토리얼 (Success) (0)	2023.10.01
[BaekJoon] 11866번 요세푸스 문제 0 문제 풀이 (Success) (0)	2023.09.30
[BaekJoon] 11478번 서로 다른 부분 문자열의 개수 문제 풀이 (Success) (0)	2023.09.28
[BaekJoon] 15651번 N과 M (3) 문제 풀이 (Success) (0)	2023.09.26
[BaekJoon] 13909번 창문 닫기 문제 풀이 (Success) (0)	2023.09.23

[BaekJoon] 11478번 서로 다른 부분 문자열의 개수 문제 풀이 (Success)

HJ0216 2023. 9. 28.

2023. 9. 28.

11478번: 서로 다른 부분 문자열의 개수

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

www.acmicpc.net

☕Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
 
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String s = br.readLine();
        Set<String> set = new HashSet<>();
 
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                set.add(s.substring(i, j));
            }
        }
 
        bw.write(set.size() + "");
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

🤔 해설

1. Set<String> set = new HashSet<>();

- 중복 제거 및 Hash 알고리즘

2. set.add(s.substring(i, j));

- 부분 문자열 추출

🔗 소스 코드
GitHub

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[BaekJoon] 11866번 요세푸스 문제 0 문제 풀이 (Success) (0)	2023.09.30
[BaekJoon] 1934번 최소공배수 문제 풀이 (Success) (0)	2023.09.29
[BaekJoon] 15651번 N과 M (3) 문제 풀이 (Success) (0)	2023.09.26
[BaekJoon] 13909번 창문 닫기 문제 풀이 (Success) (0)	2023.09.23
[Programmers] 문자열 내 마음대로 정렬하기 (Success) (0)	2023.09.22

[BaekJoon] 15651번 N과 M (3) 문제 풀이 (Success)

HJ0216 2023. 9. 26.

2023. 9. 26.

15651번: N과 M (3)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

☕Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] arr;
    public static StringBuilder sb = new StringBuilder();
 
    public static int N, M;
 
    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());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[M];
        dfs(1, 0);
 
        br.close();
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
    public static void dfs(int idx, int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
 
        for (int i = 1; i <= N; i++) {
            arr[depth] = i;
            dfs(i, depth + 1);
 
        }
    }
}
 
 

🤔 해설

1. arr = new int[M];

- 출력을 위한 arr 배열 생성

2. dfs(0);

- dfs(배열 내 위치)

3. for (int i = 1; i <= N; i++) {

- N: 입력값의 범위

4. arr[depth] = i;

- 배열 내 현재 위치에 값 입력

5. dfs(depth + 1);

- 깊은 노드로 이동

🔗 소스 코드
GitHub

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[BaekJoon] 1934번 최소공배수 문제 풀이 (Success) (0)	2023.09.29
[BaekJoon] 11478번 서로 다른 부분 문자열의 개수 문제 풀이 (Success) (0)	2023.09.28
[BaekJoon] 13909번 창문 닫기 문제 풀이 (Success) (0)	2023.09.23
[Programmers] 문자열 내 마음대로 정렬하기 (Success) (0)	2023.09.22
[Programmers] 두 정수 사이의 합 (Success) (0)	2023.09.21

이모저모 개발 블로그