0과 1의 쉼터

풀이 제한시간이 12초이기 때문에 모든 쌍을 확인하면 시간초과가 발생한다. 때문에, A~B, C~D의 합을 저장하고, Binary Search을 사용해 풀이했다. 합이 0인 쌍의 개수를 모두 구해야 하므로, 다음과 같이 upper/lower bound를 구현했다. qsort(AB, N, sizeof(int), compare); qsort(CD, N, sizeof(int), compare); long long cnt = 0; for (int i = 0; i 0) right = mid; else left = mid ..

풀이 i * j로 구성된 N x N크기의 배열의 수들을 작은 오름차순으로 나열했을 때, K번째 수가 무엇인지 알아내는 문제다. N = 3, K = 7일 때, K번째 수는 다음과 같다. K 1 2 3 4 5 6 7 i*j 1 2 2 3 4 4 6 즉 임의의 수 mid에 대해 i*j

풀이 입력받은 높이들 중에서 최대높이를 찾아 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[..

풀이 이분 탐색이란, 검색 범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘이다. 이를 사용하기 위해서는 요소들이 반드시 정렬되어 있어야 한다. 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; ..