공대생

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이 문제는 시간제한이 1000ms이기 때문에 시간 복잡도를 잘 활용해야 한다. 문제를 보자마자 이진 탐색이라는 걸 알았지만 혹시 몰라서 간단하게 코딩을 했었다. N = int(input()) NA = list(map(int, input().split())) M = int(input()) MA = list(map(int, input().split())..

- 이진탐색 이진 탐색은 데이터가 정렬되어 있는 배열에서 찾고자 하는 수를 찾아내는 방법이다. 데이터가 정렬되어 있는 배열을 data 라고 정하고 찾고자 하는 수를 target 이라고 하자. 배열의 중간 인덱스를 mid 로 정한다. 찾고자 하는 수 ( target ) 가 배열의 중간값 ( data[mid] ) 보다 크다면 우측 데이터 대상으로, 찾고자 하는 수 ( target ) 가 배열의 중간값 ( data[mid] ) 보다 작다면 좌측 데이터 대상으로 탐색을 한다. 찾고자 하는 수가 어디에 있냐에 따라 start 와 end의 위치를 변경해준다. 이러한 방법을 반복하여 찾고자 하는 수를 찾을 때까지 반복해 준다. 정리하면 이렇게 된다. ▷ target : 찾고자 하는 값 ▷ data : 오름차순으로 정..