꾸준하게 거북이처럼

알고리즘 문제를 풀다보면 시간 제한이 자주있다. for문 중복문만 쓰면 분명 시간초과 문제에 부딪히게 될 것이다🥲 이분탐색은 시간복잡도가 O(logN)으로, O(N) 보다 상대적으로 시간복잡도가 작다. 알고리즘 문제들이 보통 10,0000 입력 개수를 제한하는데, for문 중복을 쓴다면😨 시간초과해버린다. 그렇다면,, 시간복잡도 어떻게 줄일까? -> Binary Search 이분탐색을 활용해보자. 1. 이분탐색이란?? 일단 이분탐색은 오름차순 또는 내림차순을 기준으로 정렬이 되어있다는 것이 전제로, 해당 수열에서 탐색하는 알고리즘이다.  middle 인덱스를 찾고 해당 인덱스 위치에서 찾고자하는 수가 작으면 rt = mid - 1, 크다면 lt = mid + 1 이런식으로 반복을 한다. 반복문 종료 조..