본문 바로가기
728x90

전체 글74

골드바흐의 추측 - 백준 6588 [Python] 골드바흐의 추축은 아래와 같이 설명된다. 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다. 위의 문장에 3을 더하면 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다. 증명이 되어있지 않아 추측 하지만 10^18이하에서는 참인 것이 증명되어 있다. 100만 이하의 짝수가 들어왔을 때, 두 소수의 합으로 표현할 수 있는지를 알아보는 문제 Example) https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net Solut.. 2021. 7. 16.
소수 - 백준 1929 [Python] 소수의 조건 약수가 1과 자기 자신 밖에 없는 수 N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 소수를 구하는 방법 어떤 수 N이 소수인지 아닌지? N이하의 모든 소수를 구하는 방법 2. N이하의 모든 소스를 찾는 방법 : 앞서 말한 1번과정과 비슷하게 문제풀이를 한다면 N루트N의 시간복잡도가 발생한다. 이때 에라토스테네스의 체를 활용하면 더 빠르게 풀 수 있다. 2부터 N까지 모든 수를 써놓는다. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. 그 수는 소수이다. 이제 그 수의 배수를 모두 지운다. 이 문제를 해결하기 위해선, 2개의 배열이 필요하다. 수를 지웠는지 아닌지 [T/F] 소수의 목록을 유지할 배열 Example) https://w.. 2021. 7. 16.
소수 - 백준 1978 [Python] 소수의 조건 약수가 1과 자기 자신 밖에 없는 수 N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 소수를 구하는 방법 어떤 수 N이 소수인지 아닌지? N이하의 모든 소수를 구하는 방법 1. 어떤 수 N이 소수인지 아닌지? : 소수의 정의를 이용하는 방법, 약수의 특징을 이용하는 방법, 2~루트N까지 나누어 떨어지는지 (약수가 있는지 판별) 검사해 보는 방법이 있다. 이때, 직접 루트N을 구하는 것이 아니라, 값을 찾을 때 i = 2 - 루트N이기 때문에 i제곱이 N보다 작거나 같다는 범위를 사용하여 문제를 해결한다. (실수는 근사값이기 때문에, 정수의 표현을 사용하는 것이 안전) Example) https://www.acmicpc.net/problem/.. 2021. 7. 16.
최대공약수/최소공배수 - 백준 2609 [Python] 최대공약수 (GCD )를 구하는 빠른 방법은 유클리드 호제법을 이용하면 된다. a를 b로 나눈 나머지를 r이라고 했을 때 GCD(a,b) = GCD(b,r)과 같다. r이 0이면 그때 b가 최대 공약수이다. GCD(24,16) = GCD(16,8) = GCD(8,0) = 8 최소공배수 (LCM) 도 최대공약수를 구한 것과 비슷하게 적용하여 구하면 된다. LCM(A,B) = GCD(A,B) * (A/GCD(A,B)) * (B/GCD(A,B)) Example) https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net Ans.. 2021. 7. 16.
728x90

티스토리툴바