이분탐색

이분탐색은 기본적으로 탐색의 범위가 굉장히 넓을 때는 반드시 떠올려야 한다. 또한, 특정 구간의 최대, 최소값을 구하라고 할 때도 파라메트릭 서치 개념으로 접근이 가능하기 때문에 반드시 떠올려야 한다. 이분탐색은 반드시 정렬이 필요하기 때문에 리스트라면 정렬은 무조건 해야한다.

이분탐색을 사용할 때 각 파라메터의 의미는 다음과 같다.

L < R  vs  L <= R

전자는 양 끝점은 살펴보지 않겠다는 뜻이다. 후자는 양 끝점까지 살펴보겠다는 뜻이다. 

mid = (L+R)//2 vs mid = (L+R+1)//2

전자는 2개의 L,R만 탐색 범위가 남았을 때 왼쪽을 선택하겠다는 뜻이고, 후자는 오른쪽을 선택하겠다는 뜻이다. 최소, 최대 경계값을 구할 때 사용하면 된다. 

 

1. 1477 휴게소 세우기

파라메트릭 서치 개념. 
연속된 구간에서 특정 값만 유일한 값이 되기 때문에 파라메트릭 서치를 적용 가능하다. 파라메트릭 서치를 적용하는 아이디어는 이 구간을 그 값으로 설정할 수 있는지를 정하면 된다.

 

2. 2295 세수의 합

중간에서 만나기 + 이분탐색

중간에서 만나기로 전체 모수를 줄여준다. 그리고 i값을 찾기 위해 i값을 링크로 걸어준다. 그리고 같은 값을 찾아야할텐데, 전체 샘플이 너무 많기 때문에 한 샘플을 기준으로 맞는 값이 있는지 찾기 위해 이분탐색으로 접근한다. 

 

3. 9007 카누대회 

중간에서 만나기 + 이분탐색

주어진 샘플이 적당히 많고 여러개의 값이 합쳐졌을 때의 이분탐색이 필요하기 때문에 중간에서 만나기를 해서 모수를 2개로 줄여준다. 이분탐색이 필요한 이유는 탐색 범위가 굉장히 넓기 때문이다. 따라서 배열을 2개로 줄여준 후, 이분탐색을 위해 정렬을 한다. 이 후 하나의 배열에 대해서 나머지 배열을 이분탐색해서 시간복잡도를 줄인다. 시간 복잡도는 O(((N/2)^2)* logn)로 해결이 가능하다. 

 

4. 1003 K번째 수

Parametric Search

N의 값이 무척이나 크기 때문에 O(N^2)으로 직접 값을 구해서 풀 경우 메모리, 시간초과가 발생한다. 따라서, 실제로 저 값을 그리지 않고 접근할 필요가 있다. K번째수는 주어진 수열에서 몇 번째 수 인지를 각각 세면 되는 웰노운 문제이니, 어떤 기준으로 숫자를 선택해서 몇번째 수인지를 알아보고 접근할지를 접근하면 된다. 엄청나게 큰 연속 구간에서 답은 특정값이기 때문에 이분탐색, 즉 Parametric Search로 어떤 값을 선정하고 그게 몇번째 수인지를 세고, 이에 대한 논리 판단을 통해서 값을 줄여나가면 된다. 

 

5. 3151 합이 0

완전탐색 + 이분탐색

완전탐색으로 두 값을 고정시키고, 두 값을 제외한 나머지 구간에서 0을 만족하는 값이 얼마나 있는지 확인하는 방법으로 접근한다. 이 때, 조심해야 할 부분은 실력이 같은 사람들이 여러 명 존재할 수 있기 때문에 이분탐색을 Upper Bound + Lower Bound를 찾는 쪽으로 접근해야한다는 점이다. 완전탐색 + 이분탐색으로 풀 경우 O(N^2logN)으로 해결이 가능한데, N^2이다보니 코드를 제출했을 때 될 때가 있고 안 될 때가 있다. 정해는 투포인터라고 한다. 

 

6. 22116 창영이와 퇴근

BFS + 파라메트릭 서치

문제에서는 최단 경로가 아닌 경로의 경사 최소값을 묻는다. 즉, BFS는 그래프 탐색을 돕기만 하는 형태로 사용이 되어야 한다. 그렇다면 어떻게 최소값을 특정할 수 있을까? 연속된 구간에서 특정한 값을 선택하는 것이기 때문에 파라메트릭 서치로 접근하면 된다. 단, 이 문제는 시간초과 기준이 제법 빡빡해서 파라메트릭 서치 시 최대값의 기준을 입력된 값의 최대값 - 최소값으로 설정해주어야 안정적으로 문제가 해결이 된다.

 

7. 17951 흩날리는 시험지 속에서 네 평점이 느껴진거야.

파라메트릭 서치

샘플을 확인하면 O(N), O(nlogn) 수준으로 시간복잡도를 줄여야 한다. 여기서 가능한 것은 이분탐색, DP, 그리디, 정렬, 두 포인터 정도가 있다. 그러나 정렬은 할 수 없다고 명시되어있으며, 두 포인터로는 정렬된 상태가 아니기 때문에 적용을 적절하게 할 수 없다. 이분탐색으로 최소값을 설정해서 파라메트릭 서치를 했다. 

확인했을 때는 그룹을 나누는 기준이 되어야 했다. 최소값보다 클 경우, 그룹 카운트를 하나 늘려주고 그룹의 값을 초기화하면서 문제를 풀었다. 이렇게 접근한 이유는 각 그룹이 최소값 이상을 가지고 있기 때문에, 그룹이 더 많을 경우 다시 합치면 그래도 최소값 이상이기 때문에 정답에 아무런 영향을 미치지 않기 때문이다.

 

8. 13397 구간 나누기2 

파라메트릭 서치

샘플을 확인하면 시간복잡도가 가늠이 안간다. 모르긴 몰라도 시간 복잡도가 O(N^2)이상은 당연히 넘을꺼고, 그럴 경우 당연히 TLE가 발생한다. 즉, DP, 정렬, 그리디, 두 포인터, 이분 탐색 중에 하나를 써서 시간복잡도를 줄여야 한다. 그런데 정렬은 사용할 수 없으니 정렬과 두 포인터는 사용할 수 없게 된다. DP, 그리디, 이분 탐색 중에 내가 그나마 자신 있는 이분탐색으로 접근했다. 

구간 점수의 최소값을 설정해주고, 구간을 계속 나눠보는 방식으로 탐색을 한다. 이 때, 중요한 것은 구간을 그리디하게 나누었을 때, 그룹이 남거나 모자랄 때가 있을텐데 이것이 영향을 미치는지 안 미치는지를 확인해야한다. 먼저, 문제에서 주어진 분할 횟수보다 그룹을 더 많이 분할하면 케이스가 아니기 때문에 이는 배제한다. 그러면 분할 횟수보다 적게 분할 했을 때도 괜찮을지를 봐야한다.

다행스럽게도 괜찮다. 왜냐하면 분활횟수가 적어서 뒷쪽부터 하나씩 나누어 준다고 가정을 해보면, 원소를 하나씩만 가지게 되므로 구간의 최소값은 항상 0이다. 따라서, 문제에서 설정한 값보다 항상 작기 때문에 그룹을 적게 분할한 것은 문제의 정답에 영향을 주지 않는다. 

 

9. 2412 암벽등반

이분탐색 / BFS

이 문제는 BFS + 집합으로 굉장히 쉽게 풀리는 문제다. 그렇지만 나는 이걸 몰랐다. 처음에는 먼저 좌표를 정렬을 했다. 정렬한 후에, 탐색 가능한 영역을 이분탐색으로 설정하고자 했다. 즉, 조건을 만족하는 X의 Lower, Upper Bound를 구해서 그 구간에 대해서만 완전탐색을 하는 방식이었다. 그런데 이 경우, Lower + Upper Bound가 항상 포함되는 경우가 있다. 이 경우는 항상 O(N)만큼 탐색해야하기 때문에 결국 O(N^2)이 된다. 즉, 무조건 거의 TLE가 된다.

그래서 이 문제는 이분탐색으로 푸는 법을 추천하지 않는다. 그냥 처음부터 집합에 넣고, 가능한 부분을 QUE에 넣고 하나씩 삭제 하는 식으로 하면 O(N)으로 해결이 가능하다.

 

10. 16434 드래곤 앤 던전

이분탐색 + 완전탐색

모든 가능한 수 중에 최소값을 찾는 문제다. 즉, Lower Bound 문제로 치환할 수 있다. Lower Bound로 치환하면 시간복잡도는 이분탐색 + 완전탐색을 하더라도 O(nlogn)으로 해결이 가능하다. 그런데 여기서 중요한 것은 이 구간을 통과 가능한지를 확인하는 과정에서 반복문으로 하나하나 확인하게 되면, TLE가 발생한다. 이 연산을 O(1)로 하는게 중요하다.

따져보면, 딱 한 가지 경우 밖에 없다. 내가 몬스터를 죽인 시점을 확인하고, 그 시점 바로 한 칸 전에 내 피가 0을 초과하는 경우만 통과가 가능하다. 그걸 수식으로 표현해서 확인하면 끝이다. 

 

11. 16472 고냥이

이분탐색 + 슬라이딩 윈도우 / 두 포인터

특정 문자열만 읽는다고 했을 때, 만족하는 숫자는 굉장히 많으나 그 중에 최대값을 찾는 문제다. 따라서, 연속된 값들 중에 Upper Bound를 찾는 문제로 치환할 수 있다. 조건을 만족하는 Upper Bound를 찾을 때, 탐색은 Sliding Window로 접근한다. 만약, 탐색하다가 한번이라도 조건을 만족하는 것이 나온다면 Sol 함수 중에 바로 Return을 시킨다. 

중요한 점은 Sliding Window를 처음에 초기화 하는 과정도 답이 될 수 있다. 반드시 이 부분을 체크해주는 것이 맞다. 

 

12. 2585 경비행기

이분탐색 + 집합 + BFS

그래프 탐색은 집합 + BFS로 할 수 있다. 그렇다면 최소 연료통의 값이 필요하다. 최소 연료통 이상의 값들은 항상 갈 수 있기 때문에 Lower Bound를 찾는 문제로 볼 수 있다. 여기서 중요한 점은 연료통이 만약 7072가 필요하다고 하면, 708이 필요하다. 즉 10으로 나눈 후, 하나 더 크거나 같은 정수를 찾는 것이 중요함.