늘 겸손하게

랜선 자르기 이분 탐색의 응용 버전 문제 풀이 직관적으로 떠오르는 풀이는 가지고 있는 랜선들을 나눈 몫들의 합이 K가 되는 길이를 찾기 위해 길이 1부터 가장 길이가 짧은 랜선 길이까지 반복적으로 랜선들을 나누는 풀이법이다. 정답인 길이가 M 이라면 이 풀이법의 예상 복잡도는 O(NM)이다. 문제에서 N은 1이상 1,000,000 이하의 정수라고 명시했으므로 위 풀이는 시간초과가 발생한다. 그러므로 이분 탐색으로 검색 시간을 N 에서 logN으로 줄여야한다. 이분 탐색을 어떻게 적용할까? 1. left , right 설정 이분 탐색을 위해선 인덱스값을 저장할 변수 2개가 필요하다( left, right 혹은 low, high ). 위 문제에서 요구하는 답은 길이이므로 랜선의 최소 길이인 1을 left에,..

숫자 카드 2 이분 탐색의 upper bound와 lower bound를 이용하여 푸는 문제이다. upper bound 와 lower bound 란? 이분 탐색으로 배열에서 숫자를 탐색할 때 찾으려는 숫자의 개수가 배열에서 여러 개 존재할 수 있다. 이때 탐색된 동일한 숫자들중 가장 작은 인덱스 값이 lower bound, 가장 큰 인덱스 값이 upper bound이다. 예로 길이가 10이고 각 원소 값이 { 1 , 3, 5, 9 , 11 , 13 ,19 , 19 , 19 , 20 } 인 배열에서 19를 찾는다고 해보자. 19가 가장 처음 나온 인덱스는 6 , 가장 나중에 나온 인덱스는 8 이므로 lower bound는 6, upper bound는 8이 된다. 이를 이용하여 문제를 해결해야 시간 초과가 ..