첫 번째 True: 술어 이진 탐색
단조로운 예/아니요 경계를 탐색합니다
첫 번째 True: 술어 이진 탐색은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
참과 거짓의 경계를 탐색하세요
많은 문제에는 단조 조건식이 숨어 있습니다. 거짓, 거짓, 그다음에는 계속 참인 형태입니다. 이진 탐색으로 정렬된 배열 없이도 처음으로 참이 되는 위치를 찾을 수 있습니다.
# FFFFTTTT -> find first T단조가 의미하는 것
조건식이 참으로 바뀐 뒤 계속 참으로 유지되면 단조라고 합니다. 이 한 가지 성질 덕분에 경계에서 이진 탐색을 할 수 있습니다.
def ok(x):
return x * x >= target답의 범위를 설정하세요
경계를 반드시 포함하는 범위를 선택하세요. low를 가장 작은 후보로 설정하고, high는 ok가 확실히 참이 되는 값으로 설정합니다.
low, high = 0, 10**9중간을 검사하세요
mid를 정하고 ok(mid)를 호출하세요. 불리언 결과에 따라 어느 절반을 남길지 결정하며, 일반적인 이진 탐색에서 값을 비교하는 것과 같습니다.
mid = (low + high) // 2
if ok(mid):
...true이면 더 작은 값일 수도 있습니다
ok(mid)가 true라면 mid는 유효한 답이지만 더 작은 값도 가능할 수 있습니다. high = mid로 설정하여 mid를 남기고, mid - 1은 사용하지 마세요.
if ok(mid):
high = midfalse이면 더 큰 쪽으로 이동하세요
ok(mid)가 false라면 경계는 mid보다 위에 있습니다. low = mid + 1로 설정하여 mid와 그 아래의 모든 값을 버리세요.
else:
low = mid + 1low가 high보다 작은 동안 반복하세요
while low < high를 사용하고 작거나 같음 조건은 사용하지 마세요. 두 포인터가 처음으로 참이 되는 인덱스로 수렴한 뒤 반복이 멈춥니다.
while low < high:
mid = (low + high) // 2답은 low입니다
반복이 끝나면 low와 high가 같고 둘 다 처음으로 참인 값을 가리킵니다. 찾고 있던 경계로 low를 반환하세요.
return low # first x where ok(x)high = mid가 작동하는 이유
mid가 답일 수 있으므로 mid를 건너뛰면 안 됩니다. high = mid를 사용하면 범위에 mid를 남겨 두면서도 범위를 줄여 반드시 진행할 수 있습니다.
high = mid # mid stays a candidate정수 제곱근 예시
x*x가 n 이하가 되도록 하는 가장 큰 x를 찾으려면 x*x > n이 처음으로 참이 되는 위치를 탐색한 다음 하나 되돌리세요. 이 패턴은 다양한 문제에 그대로 재사용됩니다.
def ok(x):
return x * x > n
# answer is found_index - 1하나의 템플릿으로 다양한 문제 해결
이 첫 true 템플릿은 최소 가능 값, 가장 왼쪽 인덱스, 최소 용량처럼 수많은 문제를 해결합니다. 한 번 익혀 어디서나 재사용하세요.
# low<high, ok->high=mid, else low=mid+1빠른 확인
후보를 계속 살려 두는 이동이 무엇인지 정확히 짚어 보세요.
복습: 첫 true 찾기
이제 문제를 단조 조건식으로 바꾸고 경계에서 이진 탐색을 할 수 있습니다. high = mid와 while low < high를 함께 사용하는 것이 안전한 패턴입니다. 🧭
자주 묻는 질문
“첫 번째 True: 술어 이진 탐색” 강의는 무료인가요?
네 — “첫 번째 True: 술어 이진 탐색” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“첫 번째 True: 술어 이진 탐색”에서 뭘 배우나요?
단조로운 예/아니요 경계를 탐색합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“첫 번째 True: 술어 이진 탐색” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 버그 없는 고전적인 이진 탐색
- bisect_left와 bisect_right
- 첫 번째 True: 술어 이진 탐색
- 정답에 대한 이진 탐색