개발하는 고라니

2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net [이분 탐색 or Set 이용] 카테고리가 이분 탐색으로 되어있지만, 이 문제는 Set을 이용해 값이 있는지 여부를 체크하는 것도 가능하다. Set은 값을 포함하는지에 대한 시간 복잡도가 O(1)이므로 굉장히 빠르다. 다른 컬렉션인 List의 contain()은 O(N)이다. 그래서 이분 탐색을 이용한 풀이와 Set을 이용한 풀이를 해보았다. (+추가) 출력의 횟수가 최대 T * 1,000,000번 할 수 있으므로 System.out.println()을 이용한다면 메..

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) 각 지방의 예산 ..

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개의 랜선을..