판교의 메타몽

링크 : www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 이 문제에서 주의할 점은 다음과 같다. 1. 음수 값만 입력될 수도 있고, 양수 값만 입력될 수도 있다. 2. 0에 가까운 수가 정답이고, 여러개의 정답이 있으면 어떤 답을 출력해도 상관없다. 3. 따라서 반드시 0이 나오지 않아도 된다. 문제 풀이는 다음과 같다. 1. 기준 값(정답)은 나올 수 있는 값 중 가장 큰 절대값을 갖는 2,000,000,001가 된다. (..

링크 : www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 예전에 푼 적이 있던 문제였으나, 기회가 되어 다시 한번 풀었다. 이 문제에서 주의할 점은 다음과 같다. 1. 절단 높이가 나무보다 더 큰 경우에도 절단이 가능하다. ex : 나무 15, 절단 높이 20 -> 이때 나무를 자르고 남는 길이는 0으로 여긴다. 2. 때문에 절단기에 설정 가능한 높이가 아닌, 최대의 높이를 선정하는 것이 문제다. 3. 나무의 높이를 크..

이진 탐색(Binary Serach) 정의 참고 링크 : www.youtube.com/watch?v=W7RGHiN0Mmw&t=96s 1) 저장된 값을 정렬한다. 2) 왼쪽 = 첫번째 값 / 오른쪽 = 맨 마지막에 위치한 값 / 중간값 = 그 중간의 값 3) 중간값과 원하는 값의 차이에 따라 탐색하는 값의 범위를 변경해 나간다. (ex : 원하는 값이 중간값보다 크다 -> 왼쪽 = 중간값 + 1 원하는 값이 중간값보다 작다 -> 오른쪽 = 중간값 -1) 4) 원하는 답이 나올때까지 3번의 과정을 반복한다 이진 탐색(혹은 이분 탐색, 이분 검색)은 탐색 기법 중 하나이며, 원하는 값을 탐색 범위를 두 부분으로 분할하여 찾는 방식이다. 단, 이미 오름차순 혹은 내림차순으로 정렬된 구조에서 사용 가능하다는 조건..