기록보관소

랜선 자르기 문제는 이진 탐색을 활용한 문제입니다. 랜선 길이의 최소값과 최대값을 통해 가장 작게 자를 수 있는 길이, 크게 자를 수 있는 길이를 구할 수 있습니다. 이 범위 내의 길이로 랜선을 잘라서 문제에서 요구하는 개수 이상을 만들고면서 동시에 길이를 최대화하여야 합니다. 이 길이를 찾기 위해서 이진탐색을 활용합니다. 범위의 가운데 길이로 랜선을 잘랐을 때 나오는 개수가 원하는 개수보다 작다면 토막의 길이는 더욱 작아져야하므로 범위의 상한을 가운데보다 1만큼 작은 값으로 변경합니다. 잘랐을 때 나오는 개수가 많거나 같으면 가운데 길이 미만의 길이로 나누었을 때는 더 작은 토막길이로 더 많거나 같은 랜선 토막을 만들어낼 수 있다는 의미가 되므로 범위의 하한을 가운데 길이로 변경합니다. 가운데 길이보다..

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