개발하는 고라니

2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net [이분/이진 탐색, Binary Search] 우선, 이진 탐색을 하기 전 입력받은 각 지방의 예산(arr[])을 모두 더한 값과 국가예산의 총액(limit)을 비교하였다. (총액 >= 예산들의 합) 이라면 예산 중 가장 큰 값을 출력하고 종료한다. 이와 같은 경우가 아니라면 이진 탐색으로 넘어간다. init) left = 1, right = 국가예산의 총액 1) 상한선(mid) 구하기 : mid = (left + right) / n 2) 각 지방의 예산 ..

10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [해싱 + 이진 탐색 (Hashing + Binary Search)] 해싱없이 이진 탐색만으로 값을 검색하면 온전히 모든 값을 다 돌지 못한다. 예를 들어 10이 몇 개 있는지 검색을 할 때 10이 3개 있다고 가정한다면 3개를 모두 돌지 못할 수 있다. 따라서 해싱을 이용해 배열에 해당 값이 몇 개가 있는지 저장해놓으면 편리하다. 나는 다음과 같은 해싱을 사용하였다. 값의 범위는 (-10,000,000 ~ 10,000,000)이..

1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [이분 탐색] 이분 탐색 문제를 풀며 느끼는 거지만, int 보다는 long을 쓰는게 비교적 안전할 것 같다. 세심히 주의를 기울인다면 int를 사용했을 때 overflow가 나오는 것을 캐치할 수 있으나, 작은 수들을 다루다 보면 이를 무심코 지나칠 수 있는 것 같다. 이 문제의 핵심은 (1) left = 1, right = 갖고있는 랜선의 최대 길이 (2) int는 overflow가 발생하므로 long을 사용 (3) N개의 랜선을..

10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [이진 탐색, Binary Search] 그래프 문제를 주로 풀다가 문제의 스펙트럼을 좀 넓혀보고자 이진 탐색 문제를 풀기로 하였다. 이진 탐색의 기본적인 내용을 다루며 응용에 힘쓰도록 한다. 이 문제는 교과서적인 이진 탐색을 물어보는 문제이고, m개의 데이터에 대해 이진 탐색을 수행하면 되므로 딱히 어려울 것은 없어보인다. # Code import java.io.BufferedReader; import java.io.IOExcept..