분류 전체보기411 [알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes) 목차 에라토스테네스의 체란? 에라토스테네스의 체는 소수 판별 알고리즘이다. 소수란 ‘양의 약수를 두 개만 가지는 자연수’를 뜻한다. 즉, 1과 자기 자신만 약수로 가진다. 소수의 예시로는 2, 3, 5, 7, 11, 13 등이 있다. 에라토스테네스의 체는 이런 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 우선 먼저 가장 기본적인 소수 판별 알고리즘들을 살펴보겠다. 시간 복잡도 O(N) boolean isPrime(int n) { for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } 자연수 n이 소수인지 아닌지 판별하는 가장 쉬운 방법은 2부터 n - 1까지의 수로 나누어 떨어지는지 아닌지 확인하는 것이다. 이때, .. 2022. 7. 15. [백준] 1193번 : 분수찾기 – JAVA [자바] https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 문제 문제 풀이 백준 1193번 분수찾기는 브론즈 1 난이도의 수학 및 구현 문제이다. 이 문제에서는 우선 입력으로 정수 X가 주어진다. 그리고 문제에서 나와있는 것처럼 분수들이 나열되어있다. 1/1 → 1/2 → 2/1 → 3/1 → 2/2 →... 이 문제는 푸는 방식이 여러 개가 있을 수 있지만 이 글에서는 간단한 for-loop을 이용해서 풀어보려 한다. 이 문제는 분수들이 지그재그 같은 순서로 있다. 그리고 알아야 되는 것이 분수의 합이 2인 것은 1개 (1/1), 합이 3인 것은 2개 (1/2, 2/1)이고 나머지도 .. 2022. 7. 13. [백준] 1085번 : 직사각형에서 탈출 – JAVA [자바] https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 문제 문제 풀이 백준 1085번 직사각형에서 탈출은 브론즈 3 난이도의 수학 및 기하학 문제이다. 이 문제에서는 왼쪽 아래 꼭짓점 (0,0)과 오른쪽 위 꼭짓점이 (w, h)인 직사각형이 하나 있다. 그리고 한수는 이 직사각형 안에 (x, y)점에 위치해 있다. 이때 한수가 직사각형 경계선까지 가는 거리의 최솟값을 출력하면 된다. 처음에 이 문제를 읽고 보면 조금 어렵게 느껴질.. 2022. 7. 12. [백준] 2231번 : 분해합 – JAVA [자바] https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 문제 문제 풀이 백준 2231번 분해합은 브론즈 2 난이도의 브루트 포스 문제이다. 이 문제에서는 자연수 N이 주어지고 N의 가장 작은 생성자를 구해서 출력하면 된다. N의 분해합은 N과 각 자릿수의 합을 뜻한다. 예를 들어서 245의 분해합은 245 + 2 + 4 + 5 = 256이 되고 245는 256의 생성자이다. 이 문제는 브루트 포스 문제이다. 즉, 모든 숫자.. 2022. 7. 12. 이전 1 ··· 56 57 58 59 60 61 62 ··· 103 다음 반응형
