개발하자

안녕하세요 :)적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자 글을 써 내려갑니다. 백준 13909 창문 닫기이 문제는 단순 구현이 아닌 수학적인 아이디어로 접근해야 시간 초과 없이 해결할 수 있습니다.문제를 보면 머릿속에서 시뮬레이션으로 풀까? 라는 생각이들었습니다 🫣 📘 문제 💡 해결 방법1번부터 N번까지 창문이 있고, i번째 학생은 i의 배수 번호 창문의 상태를 바꿉니다.처음엔 모두 닫혀 있고, 닫혀 있으면 열고 열려 있으면 닫힙니다.그리고 마지막에 열려 있는 창문의 개수를 구하는 문제입니다.* 핵심 아이디어 *한 창문이 바뀌는 횟수는 약수의 개수이고, 약수의 개수가 홀수인 경우에만 열려있게 됩니다.그런..

안녕하세요 :)적어도 하루 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..