기록보관소

공유기 설치는 최적의 값을 찾는 문제를 참과 거짓을 결정하는 문제로 변환하여 이분법을 통해 해결할 수 있는 문제입니다. 문제의 지문을 그대로 해석하면 가장 인접한 공유기의 거리의 최대값을 구하는 문제로 생각할 수 있습니다. 이러한 최적화 문제를 참과 거짓을 결정하는 결정 문제로 변환하여 이분법을 이용하여 쉽게 해결할 수 있습니다. 위의 최적화 문제를 다음과 같은 결정 문제로 변환할 수 있습니다. "가장 인접한 공유기의 거리가 x이상이 되도록 공유기를 설치할 수 있을까" 이 질문에 대해서는 참 또는 거짓으로만 답을 할 수 있습니다. 만약 이 질문의 답이 참이라고 가정하면 가장 인접한 공유기의 거리가 x 이하인 모든 값으로 설치가 가능하다는 자명한 사실을 알 수 있습니다. 따라서 x이하의 값에 대해서는 더 ..

나무 자르기 문제는 최적화 문제를 결정 문제로 변환하여 푸는 기법을 통해 해결할 수 있는 문제입니다. 적어도 ~이상의 나무를 가져가기 위해 전기톱을 최대한으로 설정할 수 있는 높이를 구하는 최적화 문제를 참, 거짓의 결정 문제로 변환하여 이분법으로 빠르게 해결할 수 있습니다. 최대의 값을 구하기를 결정 문제로 변환하면 "나무를 어떠한 값 이하로 잘랐을 때 적어도 ~만큼 가져갈 수 있는가?"라는 질문을 할 수 있습니다. 이 질문에 대해 참, 거짓으로 답을 하게 되면 그 값을 기준으로 이하나 이상에 대해서는 더 이상 질문을 할 필요가 없어지게 됩니다. 이분법의 논리와 같다는 사실에서 이분법을 그대로 적용하여 결국에는 최적의 값을 찾을 수 있게 됩니다. 작성한 코드는 다음과 같습니다. #include #pra..

숫자 카드 2는 이진탐색을 사용하는 문제입니다. 숫자를 정렬시킨 후 이진 탐색을 하는 문제입니다. 2021.07.19 - [알고리즘/문제풀이] - [BOJ 1920번]수 찾기 [BOJ 1920번]수 찾기 수 찾기 문제는 빠른 정렬과 이진 탐색을 활용하는 문제입니다. N이 10만이기 때문에 NlogN의 시간복잡도를 가지는 정렬 알고리즘을 사용해야하며 탐색할 숫자의 개수도 10만이기 때문에 logM의 이 ark-hive.tistory.com 이전 문제와 비슷한 방법을 사용하나 테스트 케이스의 크기가 다르기 때문에 조금은 신경을 써야 했습니다. 정렬의 경우 퀵솔트의 경우 최악의 경우 N^2이 될 수 있어서 시간초과를 내었습니다. 따라서 항상 고르게 시간을 소요하는 병합 정렬을 이용해만 합니다. 이진 탐색의 경..

리스트에서 정렬된 원소 중 특정 원소를 logn 시간 내에 찾는 알고리즘이다. 혹은 특정 원소가 리스트에 없음을 확인하는 알고리즘이다. 리스트의 중간값과 찾고자 하는 값을 비교하고 만약 찾고자 하는 값이 더 크면 리스트의 하한을 중간보다 1만큼 높은 값으로 바꾸고, 더 작으면 리스트의 상한을 중간보다 1만큼 낮은 값으로 바꾼다. 탐색하는 범위를 절반씩 줄여나가면서 결국에는 원하는 값을 리스트에서 찾거나 찾지 못하게 된다. 절반씩 범위를 줄여나가므로 lgN만큼의 시간이 소요된다.

수 찾기 문제는 빠른 정렬과 이진 탐색을 활용하는 문제입니다. N이 10만이기 때문에 NlogN의 시간복잡도를 가지는 정렬 알고리즘을 사용해야하며 탐색할 숫자의 개수도 10만이기 때문에 logM의 이진 탐색 알고리즘을 사용해야 합니다. 작성한 코드는 다음과 같습니다. #include int N,M; int number[100020]; int temp; void quicksort(int low, int high) { if (low >= high) return; int pivot =number[high]; int index = low; int temp; for (int i = low;i