아이테킨의 끄적끄적

이진탐색(binary search)를 통해서 풀 수 있는 문제다. 이진탐색을 사용할 수 있는 조건은 배열이 정렬이 된 상태에서 사용할 수 있다. 또한 이진탐색은 순차적으로 탐색하는 방법보다 훨씬 빠르게 원하는 값을 찾아낼 수 있다. 시간복잡도 -> O(logN) 탐색해야하는 숫자의 수가 절반씩 줄어들기 때문에! 이진탐색은 반복문 말고도 재귀를 사용하여 구현할 수 있다. 두가지 모두 알아두고 구현해낼 수 있도록 연습해야겠다. # 1920 수 찾기 n = int(input()) list_n = list(map(int, input().split())) list_n.sort() m = int(input()) list_m = list(map(int, input().split())) # 반복문을 이용한 이진탐색 d..

먼저 이 글은 나동빈님의 '이것이 취업을 위한 코딩테스트이다' 이진탐색 파트를공부하고 정리한 것임을 밝힙니다. 순차탐색(Sequential Search) 리스트 안에서 특정 원하는 데이터를 찾으려고 할때 가장 먼저 떠올릴 수 있는 아이디어는 처음부터 하나하나 확인하면서 일치하는 데이터의 인덱스를 뽑아내는 것이다. 이를 순차탐색(Sequential Search) 이라고 한다. 반복문과 조건문을 적절히 이용하면 큰 어려움 없이 만들어볼 수 있다. 이때의 시간복잡도는 당연히 O(N)이다 이제 더 빨리 찾아낼 수 있는 이진탐색에 대해서 알아보자. 이진 탐색(Binary Search) 먼저 이진탐색은 데이터가 정렬이 되어있는 상태에서 사용할 수 있는 알고리즘이다. 이진탐색의 아이디어는 위치를 나타내는 변수 3개를..