728x90 전체 글206 [BOJ/백준] 1676 팩토리얼 0의 개수 ● [문제번호 1676] 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net ● 알아야 할 것 : 소인수분해 ● 풀이 과정 : 팩토리얼을 구하고 결과값의 끝자리부터 하나씩 0의 갯수를 세면 '시간 초과' 결과가 나온다. : 팩토리얼을 구하는 다른 방법을 생각해봤지만 다른 방법이 떠오르지 않자 문제에서 힌트를 찾으려고 하였다. 다른 숫자도 아닌 0이 끝에서부터 연속된 갯수를 찾는 문제라는 것은 10이 몇 개 곱하여 졌는가 → 소인수분해를 했을 때 2의 지수와 5의 지수를 구하여라 와 같은 문제로 이해할 수 있다. :.. 2021. 7. 28. [BOJ/백준] 10872 팩토리얼 ● [문제번호 10872] 팩토리얼 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net ● 알아야 할 것 : long long 자료형 ● 풀이 과정 : 반복문을 활용하여 구할 수 도 있고, 재귀함수를 활용하여 구할 수 있다. ● 주의 할 것 : int형의 범위를 넘을 수 있다고 우려하여 long long형으로 선언하였다. ● 참고 할 것 : NULL ● 풀이 코드 #include using namespace std; // int형의 범위를 넘을 수 있다는 우려에 long long형으로 선언 long long N; // 팩토리얼을 구하는 함수 long .. 2021. 7. 28. [BOJ/백준] 6588 골드바흐의 추측 ● [문제번호 6588] 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net ● 알아야 할 것 : vector 자료구조와 메소드 : 에라토스테네스의 체 ● 풀이 과정 : 테스트 케이스의 최댓값인 100만까지의 vector를 만들고 에라토스테네스의 체를 만들어서 소수를 모두 알아둔다. 그 다음, N = index + (N - index) 임을 이용하여 index 와 N - index 가 소수인지 판별하여 소수라.. 2021. 7. 28. [BOJ/백준] 1929 소수 구하기 ● [문제번호 1929] 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ● 알아야 할 것 : vector 자료구조와 메소드 : 에라토스테네스의 체 ● 풀이 과정 : M부터 N까지 하나씩 소수인지 확인하는 풀이를 이용하면 '시간 초과' 결과를 가져온다. : 에라토스테네스의 체를 이용하여 소수를 만들어 놓은 다음 범위에 맞는 소수들을 출력하면 된다. ● 주의 할 것 : hidden case에 M값이 1인 경우도 있으니 에라토스테네스의 체를 만들 때 기본값 설정을 꼭.. 2021. 7. 28. [BOJ/백준] 1978 소수 찾기 ● [문제번호 1978] 소수 찾기 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net ● 알아야 할 것 : 소수를 구하는 방법 ● 풀이 과정 : 2부터 확인하려고하는 수 미만까지 반복하며 나눠지는 지 확인 : 나눠지면 합성수 : 반복문이 끝날 때까지 나눠지지 않으면 소수 ● 주의 할 것 : 1은 합성수이고 반복문이 2부터 시작함으로 초기에 처리한다. ● 참고 할 것 : NULL ● 풀이 코드 #include using namespace std; int N, test, cnt; // test 값이 소수인지 확인하는 .. 2021. 7. 28. [BOJ/백준] 1934 최소공배수 ● [문제번호 1934] 최소공배수 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net ● 알아야 할 것 : 최소공배수와 최대공약수를 구하는 방법 ● 풀이 과정 : 유클리드 호제법을 이용하여 시간단축을 해야하나 싶었는데 완전탐색으로 해도 시간초과가 나지 않았다. : 최대공약수를 구한다음에 최소공배수를 계산하여 출력 ● 주의 할 것 : NULL ● 참고 할 것 : 최대공약수, 최소공배수에 대한 수학적 이해 https://dimen.. 2021. 7. 28. 이전 1 ··· 23 24 25 26 27 28 29 ··· 35 다음 728x90
