아이테킨의 끄적끄적

이분탐색(binary search)를 이용해서 풀었다. 이분탐색은 탐색 기법중 하나로 말 그대로 탐색범위를 두 부분으로 나눠서 원하는 값을 찾는 방식이다. 탐색 범위를 절반씩 줄여가면서 찾는 탐색방법이다. 따라서 시간복잡도가 하나하나 일일이 탐색하는 순차탐색보다 더 좋다. 시간복잡도 : O(logN) 이분탐색을 할 때는 먼저 정렬이 된 상태이어야 한다. dynamic programming, recursion의 개념이 녹아있다. 이분탐색 함수를 따로 정의해주고 찾아야할 리스트는 파이썬 함수로 정렬해주었다. # 10815번: 숫자 카드 n = int(input()) n_list = list(map(int,input().split())) m = int(input()) m_list = list(map(int,i..

이진탐색(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..