본문 바로가기

컴퓨터 공학99

[백준] JAVA 자바 : GCD 합 (9613번) 테스트 케이스의 개수가 주어지고, 그만큼 나올 수 있는 모든 두 쌍으로 만든 GCD의 합을 출력하는 문제이다. 사실 호제법과 static 변수만 잘 사용할 수 있다면 큰 어려움 없이 풀 수 있을 듯? 그런데 굳이 static 변수에 저장 안 해도 그냥 main 클래스에 변수 하나 생성해서 거기에 누적합 하면 더 빠를 것 같긴 한데… 난 static으로 했으니 귀찮으니까 이렇게 하자~ㅋㅋ 그런데 최대 수가 100만이기 때문에 int가 아니라 long으로 선언해줘야 한다! 난 처음에 int로 했다가 3번이나 틀렸다… 뒤늦게 깨달음……ㅋㅋㅋㅋ 여하튼 모든 경우의 수에 대해 GCD를 구해서 static long 변수에 계속해서 누적한 후 마지막에 그걸 출력하면 쉽게 해결할 수 있다. import java.io... 2024. 1. 22.
[백준] JAVA 자바 : 조합 0의 개수 (2004번) 조합을 구한 후 뒤에서부터 연속하는 0의 개수를 세는 문제이다. 앞에서 구한 팩토리얼 0의 개수와 비슷한데, 이 경우는 2의 개수도 헤아려 줘야 한다. nCm은 n! / (n-m)!m!이므로 n!의 약수의 개수에서 (n-m)!의 약수 개수와 m!의 약수 개수를 빼주면 된다. 그래서 약수 2의 개수가 5의 개수보다 적어질 수도 있어서 약수 2의 개수와 약수 5의 개수 중 더 적은 수를 반환해주면 된다. import java.io.*; import java.util.StringTokenizer; public class Combination_2004 { public static int stoi(String str) { return Integer.parseInt(str); } public static int f.. 2024. 1. 22.
[백준] JAVA 자바 : 팩토리얼 0의 개수 (1676번) 숫자 N이 주어지면, N!의 맨 뒷자리부터 돌면서 연속된 0의 개수를 구하는 문제이다. 이 알고리즘을 일일이 N마다 팩토리얼을 다 구하려고 하면 오버플로우가 발생한다. N의 최대값이 500인데, 500!은 엄청나게 큰 수이기 때문… 그렇기 때문에 팩토리얼을 구하려면 BigInteger을 쓰거나 해야 하는데 사실 BigInteger은 내 취향이 아니라서 그냥 다른 방법을 고안했다. 처음 고안한 방법은 1부터 N까지 돌면서, 그 수의 약수 중 2, 5, 10이 몇 개 들어가는지 구하는 방법이다. 기본적으로 뒷자리의 0은 약수 중 10이 포함된 개수일 테니 약수 중 10의 개수를 먼저 찾은 다음 5와 2의 개수 중 작은 수를 더해주면 연속된 0의 개수가 나온다. 그런데 여기서 조금 더 생각해보면, 10은 5가.. 2024. 1. 22.
[백준] JAVA 자바 : 팩토리얼 (10872번) 8 팩토리얼을 구하는 문제이다. 사실 팩토리얼은 기본 중에 기본인 문제라서 깃허브에만 올릴까 하다가… 글이 많아지면 나쁠 건 없으니까 그냥 블로그에도 쓴다. 사실 팩토리얼은 순환으로 구현하는 것보다는 반복으로 구현하는 게 더 효율적이라고 배웠던 것 같은데… 순환으로 구현하는 게 더 멋지니까 나는 순환으로 구현했다~ import java.io.*; public class Main{ public static int stoi(String str) { return Integer.parseInt(str); } public static int factorial(int n) { if (n==0) { return 1; } if (n==1) { return n; } else { return n * factorial(n-.. 2024. 1. 22.
[백준] JAVA 자바 : 골드바흐의 추측 (6588번) 후… 이 문제 가지고 거의 2시간 가량을 손에 쥐고 있었다… 나는 겨우 이 정도밖에 안 되는가… 문제 자체는 어려운 게 아닌데 시간 제한이 0.5초라서 상당히 타이트했다… 진짜 온갖 방법을 다 써서 나도 겨우 해결했는데 그래도 시간이 1748ms나 걸린다…ㅋㅋㅋㅋㅋ 자바 순위 600명 중 500등 정도 되는 듯…………ㅋㅋㅋㅋ쿠ㅜㅜ 나는 최대 수인 1000000까지 모두 담을 수 있는 배열을 만들고, 그 배열이 해당 수가 소수인지(true) 합성수인지(false) 나타내게 만든 다음, 이제 수 N이 들어올 때마다 3부터 차례로 2씩 증가시키면서 그 수와 N에서 그 수를 뺀 값이 모두 소수인지 확인해서 출력하는 알고리즘을 사용했다. 그런데 사실 다른 코드를 봐도 비슷한 알고리즘인 것 같은데 왜 나랑 3배 이.. 2024. 1. 22.
[백준] JAVA 자바 : 소수 구하기 (1929번) 저번 문제와 같이 이번 문제 역시 소수를 구하는 문제다. 이번에는 저번 문제에서 시도하지 못했던 에라토스테네스의 체를 이해해서 구현해 보았다… 개념이 막 어렵지는 않아서 나름 구현할 수 있었는 듯. 그런데 아무리 노력해도 180ms 이하로는 시간이 안 내려가던데… 1등 분이 120ms로 하셨던데 소스가 비공개되어 있어서 아쉽다 보고싶은데… ㅋㅋㅋㅋ 아 그리고 지금까지는 다 split()으로 나눴는데… StringTokenizer이라는 클래스가 있었으니까 이제부터는 이걸 사용하도록 하자!!! import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class GetPrimeNumber_1929 { // 소수인지 아.. 2024. 1. 22.
반응형

티스토리툴바