[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