[Java] 코딩테스트 중간 점검

문제 1: 두 수의 합

1. 문제 설명

두 정수 A와 B가 주어질 때, 두 수의 합을 출력하는 프로그램을 작성하시오.

2. 입력

첫 번째 줄에 정수 A와 B가 공백으로 구분되어 주어진다.

3. 출력

두 정수의 합을 출력한다.

제한 사항

• 1 <= A, B <= 10,000

import java.util.Scanner;

public class code01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        sc.close();

        int result = A + B;
        System.out.println(result);
    }
}

---

문제 2: 배열의 최댓값 찾기

1. 문제 설명

N개의 정수가 주어지면, 그 중 최댓값을 출력하는 프로그램을 작성하시오.

2. 입력

• 첫 번째 줄에 정수 N이 주어진다.
• 두 번째 줄에 N개의 정수가 공백으로 구분되어 주어진다.

3. 출력

N개의 정수 중 최댓값을 출력한다.

제한 사항

• 1 ≤ N ≤ 100
• 각 정수는 1 이상 1,000 이하

import java.util.Scanner;

public class code02 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < a; i++) {
            int num = sc.nextInt();
            if (num > max) {
                max = num;
            }
        }
        System.out.println(max);
        sc.close();
    }
}

---

문제 3: 자연수의 약수 구하기

1. 문제 설명

자연수 N이 주어지면, N의 모든 약수를 오름차순으로 출력하는 프로그램을 작성하시오.

2. 입력

첫 번째 줄에 자연수 N이 주어진다.

3. 출력

N의 약수를 공백으로 구분하여 오름차순으로 출력한다.

제한 사항

• 1 ≤ N ≤ 10,000

import java.util.Scanner;

public class code03 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for (int i = 1; i <= N; i++) {
            if(N % i == 0) {
                System.out.print(i + " ");
            }
        }
        sc.close();
    }
}

---

문제 4: 버블 정렬을 이용한 배열 정렬

1. 문제 설명

정수 N개의 배열이 주어지면, 버블 정렬(Bubble Sort) 알고리즘을 이용하여 오름차순으로 정렬한 결과를 출력하는 프로그램을 작성하시오.

2. 입력

• 첫 번째 줄에 정수 N이 주어진다.
• 두 번째 줄에 N개의 정수가 공백으로 구분되어 주어진다.

3. 출력

배열을 오름차순으로 정렬한 결과를 공백으로 구분하여 출력한다.

제한 사항

• 1 <= N <= 100
• 각 정수는 1 이상 1,000 이하

import java.util.Scanner;

public class code04 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 0; i < N - 1; i++) {
            for(int j = 0; j < N - 1 - i; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        for (int num: arr) {
            System.out.print(num + " ");
        }

        sc.close();
    }
}

버블 정렬 개념

• 인접한 두 원소를 비교하여 크기가 순서에 맞지 않으면 서로 교환하는 방식으로 정렬하는 알고리즘
• 가장 큰 수가 맨 뒤로 이동하면서 정렬이 진행됨

---

문제 5: 이진 탐색을 이용한 숫자 찾기

1. 문제 설명

오름차순으로 정렬된 정수 배열과 특정 정수 K가 주어질 때, 이진 탐색(Binary Search) 알고리즘을 사용하여 K의 인덱스를 찾는 프로그램을 작성하시오.
K가 배열에 없는 경우 -1을 출력한다. 단, 배열의 인덱스는 0부터 시작한다.

2. 입력

• 첫 번째 줄에 정수 N이 주어진다.
• 두 번째 줄에 N개의 정수가 공백으로 구분되어 주어진다. (오름차순 정렬)
• 세 번째 줄에 찾을 정수 K가 주어진다.

3. 출력

K의 인덱스를 출력한다. 만약 K가 배열에 존재하지 않으면 -1을 출력한다.

제한 사항

• 1 ≤ N ≤ 100
• 각 정수는 1 이상 1,000 이하

import java.util.Scanner;

public class code05 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        int K = sc.nextInt();

        int index = binarySearch(arr, K);
        System.out.println(index);

        sc.close();
    }

    public static int binarySearch(int[] arr, int K) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == K) {
                return mid;
            } else if (arr[mid] < K) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

이진 탐색 개념

• 미리 정렬된 숫자 목록에서 원하는 숫자를 빠르게 찾는 방법
• 가운데 숫자를 기준으로 탐색 범위를 절반으로 줄여가며 검색
• 존재하지 않으면 -1을 출력