팩토리얼 끝의 0의 개수는 어떻게 셀 수 있는가

1. 문제 1676번: 팩토리얼 0의 개수 (acmicpc.net) 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 끝에서 0의 개수는 어떻게 세야할까 1000000은 뒤에 0이 6개이기 때문에, $10^{6}$이라고 바로 안다. 이처럼 끝에서 0의 개수가 n개이면, $10^{n}$이라고 바로 알고 있다 다른 수를 예로 들어보면 376129000은 $376129*10^{3}$ 따라서 어떤 수에서 끝의 0의 개수는... 소인수 분해해서 10이 몇개나 있는지 계산하면 될 것이다. 여기서 10은 2와 5의 곱이므로, 소인수분해해서 2와 5의 개수가 몇개나 있는지 계산하면 될 것이다 from..

• format_list_bulleted 정수론
• · 2023. 4. 9.
• textsms

[Java]자바 매개변수 탐색 - 배열에서 특정 수를 지우고 k번째 수를 찾는 방법

1. 문제 1부터 차례대로 숫자를 적는데, 3이나 5의 배수는 숫자 대신 "Moo"라고 적습니다. 예를 들어 1부터 16까지의 숫자를 적는다면 아래와 같습니다. 1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16 이 때, N번째로 적히는 숫자는 무엇인지 구하는 프로그램을 작성해보세요. 2. 풀이 이게 쉽나?? 되게 어려운데 이분탐색에 얽매이다보니 적절한 생각이 안드네 답을 보니까 약간 소름돋았다 배열에서 K번째 수를 어떻게 찾을 수 있을까?를 생각해본다면.. 1부터 n까지 들어있는 배열 A에서, k번째 수를 나타내는 A[k]의 의미는? k이하의 수가 k개라는 뜻이다. 배열에 빈 부분이 없으니까 이게 무슨소리야? 하겠지만.. 그러면 이제 1부..

• format_list_bulleted 이분 탐색
• · 2023. 4. 7.
• textsms

[Java]예시문제로 자바 매개변수 탐색 기본기 배우기1

1. parametric search란 무엇인가1 - 합에 대한 탐색 1부터 n까지의 자연수의 합이 100이상인 경우 중 가능한 n의 최솟값을 구하는 프로그램을 작성해보세요. 단, 답은 1에서 30사이라고 가정합니다. 무작정 문제를 푼다면, 1,2,3,...,30 전까지 계속 더해보면서 최초로 합이 100을 넘는 경우, 그 숫자를 return하게 된다. 하지만 다음과 같이 시도해본다면? 1차시도: n = 15 15까지의 합은 120이므로 15는 답의 후보이며, n의 최솟값을 찾기 위해 이러한 합보다 더 작은 합은 1~14중 하나에서 찾을 수 있다. 2차시도: n = 7 7까지의 합은 28이므로, n은 확실히 7보다 커야하며, 8~14를 조사해본다. 3차시도: n = 11 11까지의 합은 66이므로, n은..

• format_list_bulleted 이분 탐색
• · 2023. 4. 5.
• textsms

이분 탐색 응용문제로 올바른 사고 연습하기2

1. 문제 18113번: 그르다 김가놈 (acmicpc.net) 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 2. 풀이 문제를 보면 김밥의 길이가 k보다 큰 경우, 양쪽을 균일하게 k씩 자른다 하지만 2k보다 짧은 경우, 한쪽 k만 자른다. k보다 작거나 같은 경우 김밥은 그냥 폐기한다 김밥 길이를 받을 때, L > k인 경우, L 2k일때, L-2k를 리스트에 저장한다 L == 2k일때는 문제에서 아무런 언급이 없기..

• format_list_bulleted 이분 탐색
• · 2023. 4. 4.
• textsms

특별한 이분탐색 -실수 구간에서도 이분탐색이 가능할까-

1. 문제 14609번: 구분구적법 (Large) (acmicpc.net) 14609번: 구분구적법 (Large) 첫 번째 줄에는 다항함수의 차수를 나타내는 양의 정수 K(1 ≤ K ≤ 10) 가 주어진다. 두 번째 줄에는 최고차항부터 내림차순으로 각 항의 계수를 나타내는 정수 ci (0 ≤ ci ≤ 10, 1 ≤ c1 ≤ 10) 가 www.acmicpc.net 2. 풀이 실제 적분값과 근삿값이 일치하게 만드는 epslion을 찾는다 그러면 실제 적분값을 먼저 구해야겠지 최대 10차 다항함수까지로 제한되어있고 다항함수 적분 방법도 힌트로 나와있다 그러면 $c_{0}x^{k} + c_{1}x^{k-1} + ... + c_{k}$를 적분하면 된다 그러면 $$\frac{c_{0}x^{k+1}}{k+1} + \..

• format_list_bulleted 이분 탐색
• · 2023. 4. 2.
• textsms

[Java]자바로 이진탐색 연습2 -올바르게 사고하기-

1. 문제 n개의 점과 m개의 선분이 주어질 때, 각 선분 위에 몇개의 점이 있는지 구하는 프로그램을 작성해보세요. 첫 번째 줄에 n과 m이 공백을 두고 주어집니다. 두 번째 줄에는 점의 좌표가 공백을 사이에 두고 주어집니다. 세 번째 줄부터 m개의 줄에 걸쳐 선분의 시작점과 끝점이 공백을 두고 한 줄에 하나씩 주어집니다. 1 ≤ n, m ≤ 100,000 1 ≤ 주어지는 수 ≤ 1,000,000,000 3 4 10 30 50 1 5 5 21 22 59 210 293 2. 풀이 아무 생각없이 사고 한다면... 선분의 시작점 끝점 예를 들어 1 5를 기준으로, 여기에 점의 좌표 10,30,50이 들어있는지 검사해보는 식으로 이렇게하면 O(MN)인가? 사실 이러면 이진탐색이고 뭐고 점의 좌표 10,30,50..

• format_list_bulleted 이분 탐색
• · 2023. 4. 2.
• textsms