Hello World

백준 2512 : 예산 문제 링크 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 내용 국가의 역할 중 하나는 여러 지방의 예산 요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산 요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이..

Lower Bound와 Upper Bound 일종의 이분 탐색(binary search) 오름차순으로 정렬되어 있을 때를 가정한다. Lower Bound -정렬된 숫자들 중에 목표값이 처음 등장하는 인덱스 값을 반환한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int lower_bound(int *arr, int key, int size) { int mid, left, right; left = 0; right = size - 1; while (left = key) right = mid; else left = mid + 1; } return right; } Colored by Color Scripter cs Upper Bound -정렬된 숫자들 중에 목표값보다 높은 숫자가 처음 등장하는..

이분 탐색 Binary Search 이분 탐색의 개념과 특징 이분 탐색(혹은 이진 탐색)은 이미 정렬된 배열에 대해 log₂N의 평균 검색 길이를 갖는 매우 빠르고 간단한 알고리즘이다. 기본 알고리즘 구간에 대해 중간값을 우선 검사한다. 중간값보다 작다면 찾는 값은 왼쪽 구간에 있다. (right = mid-1) 중간값보다 크다면 찾는 값은 오른쪽 구간에 있다. (left = mid+1) 중간값과 같다면 종료 구간을 줄여가며 1~3을 반복한다. 예제 정렬된 배열에 대해 목표값 9를 찾고자 한다. Search 1. left = 0(인덱스 위치) right = 8 mid = (0+8)/2 = 4 >>7(중간값)은 목표값 보다 작으므로 구간을 오른쪽으로 옮긴다. >>left = mid + 1 Search 2...