이진 탐색, 매개변수 탐색

1. 이진 탐색

• 정의) 데이터가 정렬되어 있는 상태에서 원하는 값 찾아내는 알고리즘

• 특징)
• 중앙값 비교를 통한 대상 축소 방식
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음
• 시간 복잡도 : O(logN)

• 과정) 오름차순 정렬일 때 (내림차순이라면 조건을 반대로 하면 됨)
1. 현재 데이터셋의 중앙값을 선택
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터 셋을 선택
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터 셋을 선택
4. 중앙값 == 타깃 데이터일 때 탐색을 종료

• 코드) 재귀로 구현 low high. 2 3 4

• 코드) 반복문으로 구현

• 팁)
• 중복값이 존재하는 배열 안에 특정 원소 반복 횟수 = key 초과의 값이 처음 나오는 위치 - key 이상의 값이 처음 나오는 위치
• 이분탐색이 멈추는 조건이 low > high인 이유
• low와 high이 동일한 순간이 탐색 범위가 1만큼인 순간인데,
• 이 때, 탐색한 그 하나의 값이 타깃과 일치하지 않으면 타깃보다 작던 크던 low > high이 됨
• 왜냐하면, 그 값이 타깃보다 작으면 low가 +1될 테고, 그 값이 타깃보다 크면 high이 -1이 되기에 뭐가 되든 low와 high은 역전됨
• 이분탐색으로 특정 타겟이 아닌 최솟값 혹은 최댓값을 찾아야 할 때
• ex. 백준 7795번) 타깃보다 작은 수 몇 개인지 구하기 5 → {1,2,5,6,7}
• mid가 타깃보다 작을 때
• 정답을 현재 mid의 위치로 갱신
• 타깃이 mid보다 크므로, 탐색 범위를 mid보다 큰 쪽으로 변경
• mid가 타깃보다 크거나 같을 때 → 핵심 : 같을 때 탐색을 마치지 않는다.
• 타깃이 mid보다 작으므로, 탐색 범위를 mid보다 작은 쪽으로 변경
• 실제론 타깃과 mid가 같은데도, 타깃을 mid보다 작다고 취급한 이유는 우리가 찾아야 하는 건 타깃 그 자체가 아닌 타깃보다 작은 값 중 가장 큰 수이기 때문임.
• 물론, 이 문제에 한해선 사실 타깃을 발견했을 때 탐색을 멈추고, 타깃 - 1을 정답으로 내놓아도 됨. 하지만 아예 이분법적으로 탐색하는 법을 배우기 위해 일단 따라 더 생각해보자. 매개 변수 탐색을 풀 때 도움이 되는 사고를 배울 수 있음.
• 여기서 타깃보다 작은 쪽을 더 탐색해서 얻을 수 있는 건, 타깃보다 작은 숫자만 있는 곳에서 이분 탐색을 실행하면 결국 계속 큰 쪽을 탐색하려 하다보니 작은 숫자들 사이에서 가장 큰 숫자 하나만 탐색 구간에 들어갔을 때 탐색이 종료됨
• 결국 원하는 결과를 얻을 수 있음. 이 원리를 아래 문제에서 더 활용해보겠음.
• ex. 매개변수 탐색) yes, yes, … no, no… 형태에서 yes 몇 개인지 구하기
• 최초로 “no”가 나오는 곳을 타깃으로 생각한다.
• mid가 yes일 때 == mid가 타깃(no가 나오는 최초 지점)보다 작을 때
• 정답을 현재 mid의 위치로 갱신
• 타깃이 mid보다 크므로, 탐색 범위를 mid보다 큰 쪽으로 변경
• mid가 no일 때 == mid가 타깃(no가 나오는 최초 지점)보다 크거나 같을 때
• 타깃이 mid보다 작으므로, 탐색 범위를 mid보다 작은 쪽으로 변경
• ex. 백준 2343번) no no, …, yes, yes… 형태에서 최초로 yes가 나오는 곳 찾기 (no 개수 + 1)
• 최초로 “yes”가 나오는 곳을 타깃으로 생각한다.

2. 매개변수 탐색 (parametric search)

• 정의) 최적화 문제를 결정 문제로 바꾸어 푸는 기법
• 최적화 문제 : 최솟값/최댓값을 요구하는 문제 (ex. 지금까지 푼 문제 중 가장 어려운 문제의 난이도는?)
• 결정 문제 : 답변이 true/false 형태로 나오는 문제 (ex. 너 실버 1 문제 풀 수 있니?)
• 최적화 문제를 결정 문제로 바꿀 수 있음 (ex. 모든 난이도에 대해 ‘너 이 난이도의 문제 풀 수 있니?’를 물어보기)

• 특징)
• 특정 파라미터를 기준으로 조건을 만족하는 부분과 만족하지 않는 경계점 탐색
• ex. 실버5~1까지 차례대로 물었을 때, 실버5~2까진 풀수 있다고 답했는데 실버 1은 못풀었다고 답하면 그 사이가 경계점임

• 과정)
1. 정답(구해야 하는 값)을 매개변수로 만들고, yes/no 문제로 바꿔보기
2. 모든 값에 대해서 yes/no를 채웠다고 생각했을 때, 정렬된 상태인지 확인하기
• yes. yes. yes. / no. no 처럼 정렬되어야 함
3. yes/no를 결정하는 문제로 해결하기
• 매개변수가 가능한 범위를 전부 배열에 넣어두고 그 배열에서 이분 탐색한단 느낌으로 짜면 됨.
• 아마, 실제로 배열을 만들어 푼다면 메모리 초과가 뜰 확률이 높은데, 그럴 땐 배열 만들지 않고 start, end, mid를 잘 활용해서 매개변수 배열의 값 다루듯 쓰면 됨 (왠만하면 이 방식으로 풀 길 권장. 너무 이해가 안될 때만 위의 배열 만드는 방식으로 풀어보기)

• 팁)
• “~의 최댓값/최솟값을 구하시오” 문제에 대해 매개 변수 탐색 시도해볼 가치가 있음
• 최적화 문제를 결정 문제로 바꾸기 == 질문의 앞뒤를 바꿔서 정답을 매개변수로 두게 하기)
• ex. 백준 2343번)
• 최적화 문제
• Q) (모든 그룹이 들어갈 수 있는) 최소 (크기)는 몇 이니? → 9~45
• A) 17
• 결정 문제
• Q) 어떤 (크기)에 (모든 그룹이 들어갈 수 있니)?
• A) O/X
• ex. 백준 2805번)
• 최적화 문제
• Q) (원하는 길이 M만큼을 얻을 수 있는) 최대 (높이)는 얼마니?
• A) 5
• 결정 문제
• Q) 어떤 (높이)로 잘랐을 때 (원하는 길이 M만큼을 얻어갈 수 있니)?
• A) O/X

💡

전체 코드와 추천 문제는 아래에서 확인하실 수 있습니다.

GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다. - GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

https://github.com/ChooSeoyeon/algorithm/tree/main