알고리즘56 [백준 1676] 팩토리얼 0의 개수 - 자바 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 풀이 뒤에 0이 되려면 10을 곱해주면 된다. 즉 5 x 2인데, 2의 배수는 5의 배수보다 무조건 많거나 같으므로 5의 배수만을 찾아주면 된다. 주의 할 점은 500 이하의 5의 배수중 25와 125는 5가 2번씩 들어가므로, 각각 2번, 3번씩 더해줘야한다. 2. 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in).. 2020. 4. 30. [백준 6588] 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모 www.acmicpc.net 1. 풀이 문제는 이해했지만, 풀이에 대해서 모호한 상태였는데 백준 강의를 통해 알게되서 정리한다. ( 갓 백준! ) 우선, 골드.. 2020. 4. 28. [백준 1929] 소수 구하기 - 자바 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 1. 풀이 기존의 소수 구하기를 통해서 입력값에 따라 2부터 하나하나 확인하면 시간초과가 발생하게 된다. 소수를 찾는데 O(n)만큼의 시간이 나오고 m만큼의 입력값이 들어오니 O(n^2)만큼의 시간이 들고, 다른 방법을 사용해도 O(n*n^1/2)만큼의 시간 복잡도 나오게 된다. 결과적으로 범위의 수에서 소수를 구하는 알고리즘인 '에라토스테네스의 체'를 통해서 구하면 된다. 만약 120까지의 소수를 구한다면, 11 * 11 > .. 2020. 4. 28. [백준 1934] 소수 찾기 - 자바 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 1. 풀이 입력값중에서 소수를 찾으면 되는 문제입니다. 2. 코드 // 기본적인 방법 import java.util.*; public class Main { // 2부터 n-1까지의 값을 나눈 나머지가 0이 아니라면 소수. public static boolean check(int n){ if(n < 2) return false; for(int i = 2; i < n; i++){ if( n % i == 0 ) return false; } return true; } p.. 2020. 4. 28. [백준 2609] 최대공약수와 최소공배수 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 1. 풀이 유클리드 호제법 을 사용하여 풀이하는 문제이다. 자세한 내용은 위 링크를 가서 확인하면 알 수 있다. 최대공약수 = 유클리드 호제법을 이용. 최소공배수 = 두 수의 곱 / 두 수의 최대공약수 2. 코드 import java.util.*; public class Main { // 최대공약수 public static int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a%b); } public static.. 2020. 4. 27. [백준 17299] 오등큰수 - 자바 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 1. 풀이 문제를 보면 [백준 17298] 오큰수 - 자바 와 비슷한 것을 볼 수 있다. '오큰수'문제에서는 사용자가 입력한 숫자를 기준으로 비교를 했다면, 이번 문제는 사용자가 입력한 숫자의 빈도를 가지고 비교를 한다. '오큰수'문제를 정확히 이해했다면, 이 문제도 금방 풀 수 있다. ( 난 쉽지 않았다... ) 여러모로 복습이 필요한 문제이다. 2. 코드 import java.io.*; import jav.. 2020. 4. 26. 이전 1 2 3 4 5 6 ··· 10 다음
