개발하자

안녕하세요 :)적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자 글을 써 내려갑니다. 백준 17103 골드바흐 파티션처음엔 단순한 소수 쌍 찾기 문제처럼 보이지만, 입력 수가 많고 범위도 크기때문에시간초과에 걸리지 않도록 효율적인 소수 판별 방법이 꼭 필요합니다. 📘 문제 💡 해결 방법문제에서 짝수 n을 입력으로 주고, 두 소수의 합으로 n을 만들 수 있는 경우의 수를 구하라고 합니다.이때 (3, 7) 과 (7, 3)은 같은 파티션으로 간주하므로 중복을 제거해야 합니다.매 입력마다 소수를 판별하는 방식은 시간초과가 나기 때문에 한 번만 소수 리스트를 전처리하는 방식인에라토스테네스의 체를 사용해야 합니다. 에라토스..

안녕하세요 :)적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자 글을 써 내려갑니다. 오늘은 에라토스테네스의 체 알고리즘에 대해 알아보려고 합니다! 📌 에라토스테네스의 체 (Sieve of Eratosthenes)소수(Prime Number)는 1과 자기 자신 외에는 나누어지지 않는 수를 말합니다.예를 들어 2, 3, 5, 7, 11 등의 소수입니다.에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 고안한 알고리즘으로,2부터 N까지의 모든 소수를 효율적으로 구할 수 있는 방법입니다. 🔍 알고리즘 아이디어1. 2부터 N까지의 숫자 리스트를 만든다2. 리스트에서 2는 소수이므로 남겨두고, 2의 배수들을 모..

안녕하세요 :)적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자 글을 써 내려갑니다. 백준 4948 베르트랑 공준이번 문제는 입력으로 주어진 n에 대해 (n, 2n) 범위의 소수 개수를 출력하는 문제입니다. 📘 문제 💡 해결 방법먼저 입력된 수 n이 0이 아닐 때까지 반복해서 입력을 받고,(n + 1)부터 2n까지의 수 중에서 소수인 수를 카운트합니다.소수 판별은 2부터 √n까지 나눠보는 방식으로 처리합니다. ✅ 풀이 및 설명 (설명은 더보기 클릭)더보기 입력은 여러 줄로 들어오기 때문에, while 루프를 통해 계속 입력을 받습니다.n == 0일 경우 입력이 끝났다는 의미이므로 종료합니다.매 입력마다 (n, 2..

안녕하세요 :)적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자 글을 써 내려갑니다. 백준 1929 소수 구하기오늘문제는 M이상 N 이하의 모든 소수를 오름차순으로 출력하는 문제입니다.M,N은 1이상 1,000,000 이하의 정수이고, M 📘 문제 💡 해결 방법M부터 N까지 모든 수를 돌면서 소수인지 판별합니다.isPrime() 함수를 이용해 √n까지만 검사해서 효율적으로 처리합니다. ✅ 풀이 및 설명 (설명은 더보기 클릭)더보기입력으로부터 M과 N을 읽어옵니다.M부터 N까지 반복하면 isPrime(i)가 true인 수 (즉, 소수)를 StringBuilder에 추가하여 출력합니다.import java.io.I..