오늘 진행된 강의에서 학습한 내용은 무엇인가요?
블랙잭 - 2798번
설명
이 문제에서는 주어진 카드 중에서 3장의 합이 목표 숫자 M을 넘지 않으면서 최대한 M에 가까운 값을 찾는 것입니다. 이를 위해 모든 가능한 3장의 카드 조합을 확인하는 브루트 포스 접근법을 사용합니다.
해결 방법
- 입력 처리: 카드의 개수 N, 목표 숫자 M, 카드 목록을 입력받습니다.
- 3중 루프 탐색: 세 개의 중첩된 for 루프를 사용하여 모든 3장의 카드 조합을 탐색합니다.
- 최대값 갱신: 각 조합의 합이 M을 넘지 않으면서 지금까지 최대값보다 크면 이 값을 업데이트합니다.
- 출력: 모든 조합을 탐색한 후, 최대값을 출력합니다.
코드
public class Main {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M;
static int[] cards;
static int maxSum = 0;
public static void main(String[] args) throws IOException{
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
cards = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){
cards[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
for(int k = j + 1; k < N; k++){
int cardSum = cards[i] + cards[j] + cards[k];
if(cardSum <= M)
maxSum = Math.max(maxSum, cardSum);
}
}
}
bw.write(maxSum + "\n");
bw.flush();
bw.close();
br.close();
}
}
타임머신 - 1440번
설명
주어진 시간 문자열에서 가능한 모든 유효한 시간 조합의 개수를 세는 문제입니다. 유효한 시간은 시(h)는 1부터 12까지, 분(m)과 초(s)는 0부터 59까지의 값이어야 합니다.
해결 방법
- 입력 처리: 주어진 시간 문자열을 입력받습니다.
- 시간 조합 생성: 가능한 모든 6가지 시간 조합을 생성합니다.
- 유효성 확인: 각 조합이 유효한 시간을 나타내는지 확인합니다.
- 카운터 증가: 유효한 시간 조합의 개수를 셉니다.
- 출력: 유효한 시간 조합의 개수를 출력합니다.
코드
import java.util.Scanner;
public class Main {
public static boolean isValidTime(int h, int m, int s) {
return (1 <= h && h <= 12) && (0 <= m && m <= 59) && (0 <= s && s <= 59);
}
public static int countValidTimeCombinations(String timeStr) {
int h1 = Character.getNumericValue(timeStr.charAt(0));
int h2 = Character.getNumericValue(timeStr.charAt(1));
int m1 = Character.getNumericValue(timeStr.charAt(3));
int m2 = Character.getNumericValue(timeStr.charAt(4));
int s1 = Character.getNumericValue(timeStr.charAt(6));
int s2 = Character.getNumericValue(timeStr.charAt(7));
int[][] combinations = {
{h1 * 10 + h2, m1 * 10 + m2, s1 * 10 + s2},
{h1 * 10 + h2, s1 * 10 + s2, m1 * 10 + m2},
{m1 * 10 + m2, h1 * 10 + h2, s1 * 10 + s2},
{m1 * 10 + m2, s1 * 10 + s2, h1 * 10 + h2},
{s1 * 10 + s2, h1 * 10 + h2, m1 * 10 + m2},
{s1 * 10 + s2, m1 * 10 + m2, h1 * 10 + h2}
};
int validCount = 0;
for (int[] combination : combinations) {
if (isValidTime(combination[0], combination[1], combination[2])) {
validCount++;
}
}
return validCount;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String timeStr = scanner.nextLine().trim();
scanner.close();
int result = countValidTimeCombinations(timeStr);
System.out.println(result);
}
}
좋은 암호 - 1837번
설명
주어진 큰 정수 K를 인수분해하여 모든 인수가 정수 L 이상의 값인지 확인하는 문제입니다.
해결 방법
- 입력 처리: 주어진 두 정수를 BigInteger 객체로 변환하여 입력받습니다.
- 인수 찾기: L보다 작은 모든 정수 i에 대해 K를 i로 나눈 나머지가 0인지를 확인하여, 인수인지를 검사합니다.
- 결과 출력: 인수를 찾으면 "BAD"와 해당 인수를, 찾지 못하면 "GOOD"을 출력합니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BigInteger K = new BigInteger(st.nextToken());
BigInteger L = new BigInteger(st.nextToken());
int N = 0;
for (int i = 2; i < L.intValue(); i++) {
if (K.remainder(BigInteger.valueOf(i)).compareTo(BigInteger.ZERO) == 0) {
N = i;
break;
}
}
String result = (N > 0) ? ("BAD " + N) : "GOOD";
System.out.println(result);
}
}
지각 - 10419번
설명
수업 시간 d가 주어졌을 때, 교수님이 최대한 지각할 수 있는 시간을 구하는 문제입니다. 지각 시간 t와 일찍 마치는 시간 s 사이에는 s = t^2의 관계가 있습니다.
해결 방법
- 입력 처리: 테스트 케이스의 수와 각 테스트 케이스의 수업 시간을 입력받습니다.
- 최대 지각 시간 찾기: 가능한 최대 지각 시간을 찾아서 출력합니다. 이는 max + (max^2) <= d를 만족하는 최대 max를 찾는 것입니다.
- 결과 출력: 각 테스트 케이스에 대해 최대 지각 시간을 출력합니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
int d = Integer.parseInt(br.readLine());
int max = 1;
while (max + (max * max) <= d) {
max++;
}
System.out.println(max - 1);
}
br.close();
}
}
이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?
알고리즘을 통해 얻을 수 있는 인사이트
1. 블랙잭 - 2798번
브루트 포스와 문제 제약 조건:
- 인사이트: 작은 입력 크기의 경우, 브루트 포스 알고리즘이 효율적이고 직관적일 수 있습니다. 비록 시간 복잡도가 O(N^3)이지만, 제약 조건(N ≤ 100)이 이를 가능하게 합니다.
- 적용: 문제의 제약 조건을 이해하는 것이 적절한 알고리즘을 선택하는 데 중요합니다. 제약 조건이 관리 가능한 경우, 브루트 포스는 간단하면서도 효과적인 해결책이 될 수 있습니다.
2. 타임머신 - 1440번
조합 생성과 유효성 검사:
- 인사이트: 모든 가능한 조합을 생성하고 유효성을 검사하는 것은 조합 수가 작고 관리 가능할 때 효과적일 수 있습니다. 이 문제는 6가지 가능한 시간 조합을 생성하고 유효성을 검사합니다.
- 적용: 입력 크기가 고정되어 있거나 매우 작은 문제에서 모든 조합을 철저히 검사할 수 있는 방법이 유용할 수 있습니다.
3. 좋은 암호 - 1837번
BigInteger와 효율적인 검사:
- 인사이트:
BigInteger
와 같은 라이브러리를 사용하면 매우 큰 숫자를 효율적으로 처리할 수 있습니다. 이 문제는 특정 범위 내에서 소수인지 확인하는 효율적인 방법의 중요성을 강조합니다. - 적용: 큰 정수가 일반적인 암호화 애플리케이션에서 이러한 접근 방식을 사용할 수 있으며, 제한된 범위 내에서 인수를 확인하는 방법이 전체 소인수분해보다 효율적일 수 있습니다.
4. 지각 - 10419번
반복 최적화:
- 인사이트: 제약 조건 내에서 최대 값을 찾는 반복 최적화가 효과적일 수 있습니다. 잠재적 해를 증가시키고 조건을 검증하여 최대 가능 값을 효율적으로 좁히는 알고리즘입니다.
- 적용: 점진적으로 조정하고 조건에 맞춰 검증해야 하는 최적화 문제에 이 접근 방식을 사용할 수 있습니다.
일반 인사이트
제약 조건 이해:
- 효과적인 알고리즘 선택은 문제의 제약 조건을 이해하는 데서 시작됩니다. 제약 조건은 단순한 알고리즘(예: 브루트 포스) 사용을 정당화하거나 더 복잡한 접근 방식을 필요로 할 수 있습니다.
조합 생성:
- 요소의 모든 가능한 조합을 생성하고 유효성을 검사하는 것은 작은 입력 크기의 문제에서 실행 가능한 전략입니다. 더 큰 크기의 경우 최적화나 대체 접근 방식(예: 백트래킹)이 필요할 수 있습니다.
BigInteger 활용:
BigInteger
를 활용하면 복잡한 작업을 크게 단순화할 수 있습니다. 특히 큰 숫자나 정밀한 연산이 필요한 경우에 유용합니다.
반복적 해 찾기:
- 최적화 문제에서 해를 반복적으로 찾고 검증하는 접근 방식은 명확한 변수 관계가 있을 때 효율적일 수 있습니다(예: 지각 문제의 ( s = t^2 )).
알고리즘 효율성:
- 주어진 제약 조건 내에서 선택한 알고리즘이 효율적으로 실행되는지 확인하는 것이 중요합니다. 문제 크기와 한계에 따라 브루트 포스 방법과 최적화된 솔루션 간의 균형을 맞추는 것이 필요합니다.
이러한 인사이트를 통해 알고리즘 문제에 명확한 전략을 가지고 접근할 수 있으며, 적절한 도구와 방법을 선택하여 효율적이고 올바른 해결책을 찾을 수 있습니다.
'스케쥴 > 스터디' 카테고리의 다른 글
[항해99 취업리부트 TIL] 4주차 4일 (1) | 2024.06.17 |
---|---|
[항해99 취업리부트 TIL] 4주차 3일 (0) | 2024.06.15 |
[항해99 취업리부트 TIL] 3주차 5일 (0) | 2024.06.10 |
[항해99 취업리부트 TIL] 3주차 4일 (0) | 2024.06.08 |
[항해99 취업리부트 TIL] 3주차 3일 (0) | 2024.06.07 |