A :순차 탐색은 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다. 순차 탐색은 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간 복잡도는 O(N)이다. Line 4에서 list의 인덱스는 0부터 시작하기에 몇 번째 원소인지를 알려주기 위해 1을 더해 리턴한다.
[7-2] Q : 재귀 함수를 이용해 이진 탐색(Binary Search)을 구현해라.
A :이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용 가능하다. 시작점, 끝점을 기준으로 가운데에 있는 중간점을 잡는다. 중간점이 실수일 때는 소수점 이하를 버려 정수로 만든다(line 5). 중간점의 원소(array[mid])와 찾으려는 수(target)을 비교해 두 수가 동일하다면 타겟의 인덱스인 mid를 return하고(line 7), 중간점의 원소가 타겟보다 크다면 중간보다 앞쪽에서 binary_search를 다시 호출한다(line 9). 반대라면 뒤쪽에서 실행한다. Line 9와 11에서 return을 안써도 될 것 같아 지워봤다. 정렬 파트에서도 재귀할 때 return을 안썼기 때문이다. 하지만 여기서는 return을 안쓰면 에러가 난다. 정렬 파트의 문제들은 어떤 값을 최종적으로 찾아내야 하는 것이 아니라, array의 원소 순서를 바꿔주는 것을 요구했다. 때문에 정렬 파트에서는 재호출하는 함수에 array가 입력되면 별도의 리턴값이 없더라도 array가 정렬된다. 하지만 이 문제에서는 line 17에서 최종적으로 하나의 값을 리턴받아 result에 저장해야 한다. 처음에는 line 9와 11에 return이 없어도 결국 최종적으로는 line 3의 return none이나 line 7의 return mid가 실행되기는 한다. 하지만 앞 단에서 호출한 함수로 해당 리턴 값이 전달되지 못하기 때문에, 결국 처음 호출을 시작한 함수에도 리턴 값이 전달되지 않는다. 이진 탐색 알고리즘은 한 단계를 거칠 때마다 확인해야 할 원소가 평균적으로 절반으로 줄어들기에 시간복잡도는 O(logN)이다.
[7-3] Q : 이진 탐색(Binary Search)을 반복문으로 구현하라.
A :7-2의 코드와 원리는 동일하지만, line 2에서 범위가 이탈되지 않는 한 계속해서 line 7, line 8에서 start나 end의 범위가 줄어들고, 다시 line 3에서 mid의 값도 새롭게 조정된다. 만약 원소가 3, 4 두 개만 있고, 4가 target이라면, array[start]==3, array[end]==4이므로 array[mid]==3이다. 때문에 line 8에서 start = mid+1 = end가 되고, line 2에서 start==end가 된다. 따라서 line 2에서 <=로 등호를 넣어줘야 한다. 코딩 테스트에서 처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내는 알고리즘을 사용하는 것이 좋다.
[7-4] Q : readline() 함수를 이용해 입력을 받아 출력하는 프로그램을 작성해 보자.
A :데이터의 수가 1000만개를 넘어가거나 탐색 범위의 크기가 1000억 이상이라면 이진 탐색 알고리즘을 의심해 볼 수 있다. 하지만 이렇게 입력 데이터의 개수가 많은 문제에 input() 함수를 사용하면 속도가 느려 시간 초과가 될 수 있다. 이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용해 시간 초과를 피할 수 있다. 이 코드는 외워서 사용하자. rstrip()함수도 꼭 써줘야 하는데, readline()으로 입력하면 엔터가 줄바꿈 기호로 입력되는데, 이 공백 문자를 제거하는 역할을 해준다.
[7-5] Q : 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 구매하려 한다. 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성하라. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5, [8,3,7,9,2]. 손님은 총 3개의 부품이 있는지 확인을 요청하는데, 부품 번호는 다음과 같다. M=3, [5,7,9]. 이때, 손님이 요청한 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 첫째 줄에는 N이 주어진다(1~1,000,000). 둘째 줄에는 공백으로 구분해 N개의 정수가 주어진다. 셋째 줄에는 M이 주어진다(1~100,000). 넷째 줄에는 공백으로 구분해 M개의 정수가 주어진다.
A :이 문제는 여러 방식으로 풀 수 있다. 위 코드는 이진 탐색으로 푼 경우다. 우선 N_을 정렬해줘야 한다(line 6). 그 뒤 M_ 안의 각 원소들에 대해 이진 탐색을 진행해 준다. 이 경우, N_을 정렬하는데는 O(NlogN)의 시간이 필요하다. 대략 2000만 번의 연산이다. 그리고 탐색 과정에는 O(MlogN)으로 약 200만번의 연산이 필요하다. 결국 정렬하고 이진탐색을 진행하는데는 O((M+N)logN)이 필요하다.
이 코드는 이진 탐색이 아닌 계수 정렬을 이용한 코드다. 모든 원소의 번호를 포함할 수 있는 크기의 리스트(N은 최대 1,000,000)를 만든 뒤, 해당 리스트의 인덱스에 접근해 부품이 있는지 확인하면 된다.
또한, 이 문제는 특정 수가 한 번이라도 등장했는지만 검사하면 되므로 집합(set) 자료형을 이용해 풀 수 있다. 집합 자료형은 단순히 특정 데이터가 존재하는지 검사할 때 효과적으로 사용할 수 있다. 소스의 간결한 측면에서는 가장 우수하다. set을 사용하면 in을 사용할 수 있어 편리하다.
[7-6] Q : 떡 가게에서 만든 떡의 길이가 일정하지 않다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H의 윗부분이 잘릴 것이고, H보다 짧은 떡은 잘리지 않을 것이다. 예를 들어, 높이가 19,14,10,17인 떡이 있고, H를 15로 지정하면 떡의 길이는 15,14,10,15가 될 것이고, 잘린 떡의 길이는 4,0,0,2가 될 것이다. 이 때 손님은 총 6의 길이를 가져간다. 손님이 요청한 길이가 M일때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성해라. 첫째 줄에 떡의 개수 N(1~1,000,000)과 M(1~2,000,000,000)이 주어진다. 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이다. H는 정수이다.
A :처음에는 이런 식으로 문제를 풀었다. H를 떡의 길이들 중 가장 긴 것으로 초기값을 잡고, 1씩 줄여가며 적절한 높이를 찾는 것이다. 하지만 이 방식으로 위 문제를 접근하는 것은 적절하지 못하다.
이 문제는 전형적인 이진 탐색 문제이자, 파라메트릭 서치(Parametric Search) 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 결정문제(yes or no)로 바꾸어 푸는 방법이다. '원하는 조건을 만족하는 가장 알맞는 값을 찾는 문제'에 주로 파라메트릭 서치를 이용한다. 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면, 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다. 이진 탐색으로 절반씩 탐색 범위를 좁혀 나가는 것이다. 절단기의 높이(탐색 범위)는 1부터 10억까지의 정수 중 하나인데, 이처럼 큰 수를 보면 당연히 이진 탐색을 먼저 떠올려야 한다. 절단기의 높이 범위가 작다면 순차 탐색으로도 해결할 수 있지만, 큰 범위에서는 시간 초과를 받을 것이다. 반면 H를 이진 탐색으로 찾는다면, 약 31번 만에 모든 경우의 수를 고려할 수 있다. 이 때 N이 최대 100만개이므로 H를 바꾸며 모든 떡을 체크하는 경우, 대략 최대 3000만 번 정도의 연산으로 풀 수 있다.
H는 가장 긴 떡의 길이 안에 있어야 한다(line 5). 처음에는 start는 0, end는 19로 시작한다. mid는 9다. 하지만 떡의 합은 10+6+1+8=25로 6보다 크다. 때문에 우선 result에 9를 저장해 두고 10~19 범위에서 탐색을 다시 진행한다(line 17). 그럼 mid는 14고, 여전히 5+1+3=9로 6보다 크다. 때문에 새로운 result에 14를 저장하고 15~19 범위에서 탐색을 진행한다. 이렇게 하다 보면 start는 15, end는 16이 되는데, mid는 15이므로 역시 result에 15가 저장되고, start는 16이 된다. 이제 line 6에 의해 break되어 15가 출력된다. 처음에는 line 16에서 result를 저장해주는 과정에서, total이 M보다 크거나 같은 것은 맞지만, 최적의 값이 아닌 값이 result에 저장되어도 괜찮을까 했지만, 이 코드는 result 값을 한 번 찾더라도 멈추지 않고, start와 end값이 일치할 때까지, 즉, 모든 범위에 대해 탐색을 진행하기 때문에 결국에는 최적의 H값이 result에 저장된다. 중간점의 값은 시간이 지날수록 최적화된 값을 찾기 때문이다. 이 문제에서는 현재 얻을 수 있는 떡의 양에 따라 자를 위치를 정해야 하기 때문에 재귀적으로 구현하는 것이 귀찮을 수 있다. 때문에 이 문제와 같은 파라메트릭 서치 문제 유형은 이진 탐색을 재귀적으로 구현하기 보다 반복문을 이용해 구현하는 것이 더 편리하다.
[7-7] Q : N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이 때 수열에서 x가 등장하는 횟수를 계산해라. 예를 들어 {1,1,2,2,2,2,3}에서 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다. 단, 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과를 받는다. 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력된다(1~N~1,000,000, -10^-9~x~10^9). 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력된다. 수열의 원소 중 값이 x인 원소의 개수를 출력해라. 단, 하나도 없다면 -1을 출력해라.
A :이 문제는 일반적인 선형 탐색으로는 시간 초과 판정을 받는다. 하지만 데이터가 정렬되어 있기 때문에, 이진 탐색을 수행할 수 있다. 특정 값이 등장하는 첫째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제를 해결할 수 있다. 표준 라이브러리인 bisect_left와 bisect_right을 이용해 count_by_range 함수를 정의한다. 이 함수는 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수이다. bisect_left는 array에서 입력된 값이 있는 가장 왼쪽의 index를 반환하고, bisect_right는 array에서 입력된 값이 있는 가장 오른쪽의 index를 반환한다. 각각에 대해 이진 탐색을 진행하는 것이다.
