알고리즘 별 문제 정리/정수론 (2) 썸네일형 리스트형 [C++] 백준 4134: 다음 소수 문제 이해- 정수 n이 주어졌을 때 n이상인 소수를 출력하라. - 시간 제한: 1초- 메모리 제한: 128MB T: 테스트 케이스 개수n: 정수 (0 ~ 4 * 10^9) 각각의 테스트 케이스에 대하여 n 이상인 소수를 출력하라. 문제 풀이처음에는 소수 문제라서 에라토스테네스의 체를 생각했는데n의 최댓값이 4 * 10^9으로 메모리 제한에 걸릴거 같았다. 다음으로 생각한게 1부터 n까지 탐색하는 완전 탐색인데이 방법 역시 O(n)의 시간복잡도로는 시간초과일것 같았다. 결국 인터넷을 참고하여 풀었는데핵심은 바로 이것이다.어떠한 값에 대하여 소수를 판단할 때, 그 값의 약수들의 곱은 그 값의 제곱근을 기준으로 대칭이기 때문에 제곱근 이하의 값 까지만 검사를 하면 나머지는 검사를 할 필요가 없다 즉, s.. [C++] 백준 2004: 조합 0의 개수 문제 이해- nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하라. - 시간 제한: 2초- 메모리 제한: 128MB - 정수 n, m(0 ~ 2,000,000,000, 10^9, n != 0) - 첫째 줄에 nCm의 끝자리 0의 개수 문제 풀이끝자리 0의 개수는 소인수 중 2와 5의 개수로 구할 수 있다!둘 중 작은 것의 개수가 바로 끝자리 0의 개수이다. nCm = n! / (n-m)! m! 이다.즉, n!의 소인수 개수에서 (n-m)!과 m!의 소인수 개수를 빼주면 nCm의 소인수 개수가 나올 것이다. 그럼 n!의 소인수(k) 개수는 어떻게 구할 수 있을까?일반적인 반복문을 사용하면 수의 크기가 워낙 크기에 시간 초과에 걸릴 수밖에 없다. 정답은 n을 k의 지수들로 나누어주는 것이다.이.. 이전 1 다음