스케쥴/스터디
[항해99 취업리부트 TIL] 4주차 4일
hyeseong-dev
2024. 6. 17. 21:26
오늘 학습한 내용은 무엇인가요?
적어도 대부분의 배수
- 문제 요약: 주어진 정수 배열에서 세 수의 조합을 생성하고, 이 조합들 중 최소 공배수를 계산하여 가장 작은 최소 공배수를 찾는 문제입니다.
- 해결 방법 요약:
- 입력 처리:
- 버퍼에서 입력을 읽어와 정수 배열로 변환합니다.
- 조합의 크기 계산:
- 조합 공식인 ( N! / ((N-R)! \times R!) )를 사용하여 조합의 크기를 계산합니다.
- 조합 생성:
- 세 수의 모든 조합을 생성하고 배열에 저장합니다.
- 최소 공배수 계산:
- 생성된 각 조합에 대해 최소 공배수를 계산하고, 결과를 배열에 저장합니다.
- 최소값 찾기:
- 최소 공배수 배열에서 가장 작은 값을 찾아 출력합니다.
- 입력 처리:
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을 세 번, 이런 식으로 수열을 만들고 주어진 구간의 합을 구하는 문제입니다.
- 해결 방법 요약:
- 입력 처리:
- 구간의 시작과 끝을 입력받습니다.
- 수열 생성:
- 수열을 생성하여 주어진 구간의 합을 구하기 위해 필요한 부분만 유지합니다.
- 구간 합 계산:
- 생성된 수열에서 주어진 구간의 합을 계산하여 출력합니다.
- 입력 처리:
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번 문어와 3번 문어가 2번 손을 잡고, 이러한 식으로 진행합니다.
- 결과 출력:
- 생성된 수열을 출력합니다.
- 입력 처리:
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. 성능과 메모리 사용 고려
알고리즘을 설계할 때 성능과 메모리 사용을 항상 고려해야 합니다.
- 시간 복잡도: 각 알고리즘의 시간 복잡도를 분석하고, 가능한 효율적인 알고리즘을 선택했습니다. 예를 들어, "적어도 대부분의 배수" 문제에서는 조합 생성과 최소 공배수 계산의 시간 복잡도를 고려했습니다.
- 메모리 사용: "문어" 문제에서는 메모리 사용을 최소화하기 위해 배열을 사용하여 사전순으로 가장 앞서는 수열을 생성했습니다.