이분 탐색14 [백준 2805] 나무 자르기 [C] 풀이 입력받은 높이들 중에서 최대높이를 찾아 last로 지정하고, 절단기로 자를 나무의 높이(mid)를 기준으로 이분탐색을 사용해 풀이했다. mid보다 높은 높이의 나무만 자르며 필요한 M미터를 충족시킬때 result로 갱신해주었다. 소스코드 #include int arr[1000001]; int main(){ int N, M; long long last = 0; scanf("%d %d", &N, &M); for (int i = 0; i < N; i++){ scanf("%d", &arr[i]); last < arr[i] && (last = arr[i]); } long long temp = 0, result = 0, first = 0, mid; while (first mid && (temp += (arr[.. 2021. 7. 29. [백준 1920] 수 찾기 [C] 풀이 이분 탐색이란, 검색 범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘이다. 이를 사용하기 위해서는 요소들이 반드시 정렬되어 있어야 한다. N개의 정수를 Quick Sort로 정렬해준 후, M개의 정수를 입력받음과 동시에 Binary Search로 탐색해 해결했다. Binary Search의 Big-O는 O(log2n)이지만, n은 최대 100,000으로 재귀 함수로 구현해도 Stack Overflow가 발생하지 않기 때문에 재귀적/비재귀적 방법으로 둘 다 사용 가능하다. 소스코드 #include #include int compare(const void *a, const void *b){ int n1 = *(int *)a, n2 = *(int *)b; if (n1 < n2) return -1; .. 2021. 7. 15. 이전 1 2 3 다음
