본문 바로가기

백준 알고리즘 단계별 풀이 (문제 수)72

[C++] 베르트랑 공준 : 4948번 문제 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 시간제한 : 1초 입력범위 : 1 ≤ n ≤ 123,456 해석 문제를 풀기 위해서는 '에라토스테네스의 체' 를 알아야만 한다. 이걸 몰라도 구현과 결과는 나오겠지만, 백준 사이트에서 시간초과가 날 것이다. 에라토스테네스의 체는 생각보다 별거없다. 구하고자 하는 범위까지의 소수를 구하는 알고리즘이다. 방법은 다음과 같다. 1. 구하고자 하는 범위의 모든 숫자를 나열한다. 2. 2의 두번째 배수(4) 부터 시작하여 2의 배수를 모두 제거한다. 3. 3의 두번째 배수(6) 부터 시작하여 3의 배수를 모두 제거한다. 4. 이 과정을 반복하여 어떤 소수의 모든 배수를 제거한다. 5. 범위 내에는 소수.. 2022. 7. 6.
[C++] 소수 구하기 : 1929번 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 예제 입력 3 16 예제 출력 3 5 7 11 13 해석 소수를 판별하는 방법은 아래 링크를 참고한다. [C#] 소수 찾기 : 1978번 (tistory.com) [C#] 소수 찾기 : 1978번 이번 문제는 C# 으로 구현하였습니다! 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 해석 소수가 되기 위해선 1과 자기자신으로만 나누어져야 한다. 바 wildgoosechase.tistory.com 풀이 #include #include using namespace std; int main() { int M, N; // 범위 bool isPrime = true; cin >> M >> N; for (int i.. 2022. 7. 6.
[C++] 소인수분해 : 11653번 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. N이 1인 경우 아무것도 출력하지 않는다. 예제 입력 72 예제 출력 2 2 2 3 3 해석 어떤 수 N을 소인수 분해한다는 것은 소수들의 곱으로만 이루어지도록 만드는 것을 의미한다. 따라서 가장 작은 소수 2부터 나누어 떨어진다면 소인수분해를 1차례 진행한 것이다. 반복적으로 2 와 N - 1 사이까지 나누면서 나누어 떨어지는 시점이 발생하면, 나누어서 얻은 새로운 몫인 N 과 새로운 연산을 하며 N이 더이상 나누어지지 않을 때 까지 진행하면 된다. 마지막으로는, 최종으로 남은 N 까지 출력하면 소인수분해가 완료된다. 풀이 #include #include using namespace std; int main() { int N; // 주.. 2022. 7. 6.
[C++] 소수 (제곱근을 활용하여 소수 판별) : 2581번 문제 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 문제 해석 이전 문제와 동일한 방법으로 소수를 판별하면 된다. 단 범위를 입력받으므로, 반복문의 범위를 입력받은 값으로 설정해주는 것과 소수들을 모두 더한 합, 그리고 최솟값을 추가로 출력해주면 된다. + 소수를 판별함에 있어서 2 ~ 자기자신 사이의 모든 수로 나누어보아도 되지만, 2 ~ 자기자신의 제곱근까지만 나누어보면 더 빠르게 판별할 수 있다. 12의 경.. 2022. 7. 5.
[C#] 소수 찾기 : 1978번 이번 문제는 C# 으로 구현하였습니다! 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 해석 소수가 되기 위해선 1과 자기자신으로만 나누어져야 한다. 바꿔말해, 2와 자기 자신 - 1 사이의 숫자로 나누었을 때, 나머지가 0 이 아니면 소수가 아니다. 따라서, 입력받은 수를 2부터 입력받은 수 까지 나누어 나머지가 생기면 소수가 아니라고 판별하고, 그 외의 경우만 소수로 갯수를 세면 된다. 하지만, 2부터 자기자신 - 1 까지 일일히 확인하는 것보다 계산 속도를 줄일 수 있는 방법이 존재한다.이는 다음 링크를 참고하면 알 수 있다. [C++] 소수 (제곱근을 활용하여 소수 판별) : 2581번 (tistory.com) [C++] 소수 (제곱근을 활용하여 소수 판별) .. 2022. 7. 5.
[C++] 큰 수 A + B : 10757번 문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 예제 입력 9223372036854775807 9223372036854775808 예제 출력 18446744073709551615 문제 풀이 매우 큰 두 수의 합을 출력해야 하므로 일반적인 방법으로는 계산할 수 없을 것이다. 따라서, 숫자를 문자열로 입력받아 각 자리 수마다 직접 더해서 올림하는 연산을 구현해야 한다. 이 때, 출력은 한 글자씩 출력해도, 전체를 출력해도 정답처리 된다. 또, 숫자의 입력은 01 + 2 와 같은 형식으로도 입력이 가능하지만 출력은 맨 앞 자리의 0을 생략해야 한다. #include using namespace std; int main() { string a, b; // 입력받는 두 수 int.. 2022. 7. 4.

티스토리툴바