[Data Structure] 이분 탐색(Binary Search)
● 순차 탐색 알고리즘과 시간 복잡도 탐색이란, 수많은 데이터 속에서 내가 원하는 데이터를 찾는 과정을 말합니다. 예를 들어 1부터 100까지의 숫자가 적힌 배열에서 31을 찾는 것은 탐색을 거쳐야 할 것입니다. 그중 순차 탐색이란, 처음부터 끝까지 찾고자 하는 데이터를 탐색하는 것을 말합니다. 순차 탐색 알고리즘을 구현하면 다음과 같습니다. int LSearch(int arr[], int len, int tar) { for (int i = 0; i < len; i++) { if (arr[i] == tar) { return i; } } return -1; } int main(void) { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int length = sizeof(..
2023. 4. 10.
[이분 탐색] 백준 10815번 (파이썬) : 숫자 카드
이 문제 같은 경우에는 카드를 하나하나 비교해야 하기 때문에 이분 탐색을 사용합니다. N = map(int, input()) my_card = sorted(map(int, input().split())) M = map(int, input()) num_card = list(map(int, input().split())) answer = [] def binary(k, my_card, start, end): mid = (start+end) // 2 if start > end: answer.append(str(0)) elif k == my_card[mid]: answer.append(str(1)) elif k > my_card[mid]: binary(k, my_card, mid+1, end) else: bina..
2023. 4. 5.
