본문 바로가기

컴퓨터 공학/백준75

[백준] 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.
[백준] JAVA 자바 : 소수 찾기 (1978번) 제목과 같이 소수를 찾는 문제이다. 사실 에라토스테네스의 체 알고리즘을 써야 할 것 같은데… 나는 그런 개념이 존재한다는 사실을 이 문제를 다 풀고 나서야 알았다…ㅋㅋㅋㅋㅋ 다음 문제가 소수 구하기던데, 그 문제를 풀 때 에라토스테네스의 체를 써봐야겠다! import java.io.*; public class PrimeNumber_1978 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int N = stoi(br.readLine()); in.. 2024. 1. 21.
[백준] JAVA 자바 : 최소공배수 (1934번) 앞에서 GCD와 LCM을 찾는 문제를 풀었지만… 문제를 다시 보니 이상하게 나만 300ms대가 나오는 것이었다… 분명 다른 분들은 80~150ms가 걸리시는데… 왜 나만 이렇게 비효율적이게 돌아가는 거지?? 그래서 다른 분들의 코드를 참조했는데, 나는 바보같이 for문을 계속 돌려서 GCD와 LCM을 찾았지만 유클리드 호제법으로 더 간단하게 GCD와 LCM을 찾을 수 있었다. 유클리드 호제법 GCD: 두 수 a와 b를 받으면, a에서 b를 나눈 나머지가 0이될 때의 b가 GCD이다. 0이 나올 때까지 반복하면 된다. LCM: 두 수 a와 b를 받으면, a와 b를 곱한 값에서 GCD를 나눈 값이 LCM이다. ((a*b) / gcd) import java.io.*; public class LCM_1934 {.. 2024. 1. 21.
반응형

티스토리툴바