[항해99 취업리부트 TIL] 4주차 4일

오늘 학습한 내용은 무엇인가요?

적어도 대부분의 배수

• 문제 요약: 주어진 정수 배열에서 세 수의 조합을 생성하고, 이 조합들 중 최소 공배수를 계산하여 가장 작은 최소 공배수를 찾는 문제입니다.
• 해결 방법 요약:
  1. 입력 처리:
     • 버퍼에서 입력을 읽어와 정수 배열로 변환합니다.
  2. 조합의 크기 계산:
     • 조합 공식인 ( N! / ((N-R)! \times R!) )를 사용하여 조합의 크기를 계산합니다.
  3. 조합 생성:
     • 세 수의 모든 조합을 생성하고 배열에 저장합니다.
  4. 최소 공배수 계산:
     • 생성된 각 조합에 대해 최소 공배수를 계산하고, 결과를 배열에 저장합니다.
  5. 최소값 찾기:
     • 최소 공배수 배열에서 가장 작은 값을 찾아 출력합니다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] intArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int lcmSize = combinationSize(intArr.length, 3);
        int[][] combinations = generateCombinations(intArr, lcmSize, 3);

        int answer = Arrays.stream(combinations)
                .mapToInt(comb -> lcm(comb[0], comb[1], comb[2]))
                .min()
                .orElseThrow();

        System.out.println(answer);
    }

    static int gcd(int numA, int numB) {
        while (numB != 0) {
            int temp = numB;
            numB = numA % numB;
            numA = temp;
        }
        return numA;
    }

    static int lcm(int numA, int numB) {
        return (numA * numB) / gcd(numA, numB);
    }

    static int lcm(int numA, int numB, int numC) {
        return lcm(lcm(numA, numB), numC);
    }

    static int combinationSize(int n, int r) {
        return factorial(n) / (factorial(n - r) * factorial(r));
    }

    static int[][] generateCombinations(int[] arr, int size, int r) {
        int[][] combinations = new int[size][r];
        int idx = 0;

        for (int i = 0; i < arr.length - 2; i++) {
            for (int j = i + 1; j < arr.length - 1; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    combinations[idx++] = new int[]{arr[i], arr[j], arr[k]};
                }
            }
        }

        return combinations;
    }

    static int factorial(int n) {
        if (n == 0) {
            return 1;
        }

        int[] table = new int[n + 1];
        table[0] = 1;

        for (int i = 1; i <= n; i++) {
            table[i] = i * table[i - 1];
        }

        return table[n];
    }
}

쉽게 푸는 문제

• 문제 요약: 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 수열을 만들고 주어진 구간의 합을 구하는 문제입니다.
• 해결 방법 요약:
  1. 입력 처리:
     • 구간의 시작과 끝을 입력받습니다.
  2. 수열 생성:
     • 수열을 생성하여 주어진 구간의 합을 구하기 위해 필요한 부분만 유지합니다.
  3. 구간 합 계산:
     • 생성된 수열에서 주어진 구간의 합을 계산하여 출력합니다.

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

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

    static int sumOfSubsequence(int A, int B) {
        int sum = 0;
        int count = 0;

        for (int i = 1; i <= B; i++) {
            for (int j = 0; j < i; j++) {
                count++;
                if (count >= A && count <= B) sum += i;
                if (count == B) break;
            }
        }
        return sum;
    }
}

문어

• 문제 요약: 문어들이 손을 맞잡고 원을 만들 때, 인접한 두 문어가 잡은 손의 번호를 이용하여 사전순으로 가장 앞서는 수열을 찾는 문제입니다.
• 해결 방법 요약:
  1. 입력 처리:
     • 문어의 수를 입력받습니다.
  2. 수열 생성:
     • 사전순으로 가장 앞서는 수열을 생성합니다. 예를 들어, 1번 문어와 2번 문어가 1번 손을 잡고, 2번 문어와 3번 문어가 2번 손을 잡고, 이러한 식으로 진행합니다.
  3. 결과 출력:
     • 생성된 수열을 출력합니다.

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();

        int[] ans = new int[n];

        for (int i = 0; i < n / 2; i++) {
            ans[2 * i] = 1;
            ans[2 * i + 1] = 2;
        }

        if (n % 2 != 0) {
            ans[n - 1] = 3;
        }

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

얻은 인사이트는 무엇인가요?

이번 세 가지 알고리즘 문제를 해결하면서 얻은 인사이트는 다음과 같습니다:

1. 문제 해결의 체계적인 접근 방식

각 문제를 해결하는 데 있어 체계적인 접근 방식이 중요함을 다시 한번 깨달았습니다. 문제를 해결할 때는 다음과 같은 단계로 접근할 수 있습니다:

• 문제 분석: 문제의 요구사항을 명확히 이해하고, 해결해야 할 목표를 설정합니다.
• 입력 처리: 입력 데이터를 효율적으로 처리할 방법을 설계합니다.
• 핵심 알고리즘 설계: 문제를 해결하기 위한 핵심 알고리즘을 설계합니다.
• 결과 출력: 최종 결과를 원하는 형식으로 출력합니다.

2. 조합과 순열의 효율적 사용

조합과 순열은 많은 문제에서 중요한 역할을 합니다. 특히, "적어도 대부분의 배수" 문제에서 조합을 생성하고 최소 공배수를 계산하는 과정에서 이를 잘 활용할 수 있었습니다.

• 조합 생성: 조합 공식 ( N! / ((N-R)! \times R!) )을 사용하여 조합의 크기를 계산하고, 이를 기반으로 조합을 생성했습니다.
• 최소 공배수 계산: 두 수 또는 세 수의 최소 공배수를 효율적으로 계산하는 알고리즘을 활용했습니다.

4. 성능과 메모리 사용 고려

알고리즘을 설계할 때 성능과 메모리 사용을 항상 고려해야 합니다.

• 시간 복잡도: 각 알고리즘의 시간 복잡도를 분석하고, 가능한 효율적인 알고리즘을 선택했습니다. 예를 들어, "적어도 대부분의 배수" 문제에서는 조합 생성과 최소 공배수 계산의 시간 복잡도를 고려했습니다.
• 메모리 사용: "문어" 문제에서는 메모리 사용을 최소화하기 위해 배열을 사용하여 사전순으로 가장 앞서는 수열을 생성했습니다.