반응형
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
import sys
def binary_search(find_list, item, start, end):
if start > end:
print(0)
else:
mid = int((start+end)/2)
if item == find_list[mid]:
print(1)
elif item < find_list[mid]:
end = mid -1
return binary_search(find_list, item, start, end)
elif item > find_list[mid]:
start = mid + 1
return binary_search(find_list, item, start, end)
if __name__ == '__main__':
N = int(input())
A = sorted(list(map(int,sys.stdin.readline().split())))
M = int(input())
B = list(map(int,sys.stdin.readline().split()))
for i in B:
binary_search(A, i, start=0, end=N-1)
위 문제를 그냥 풀려고 하면
시간 초과가 됩니다.
따라서 Binary search(이진 탐색) 알고리즘을 사용하여야 합니다.
그에 대한 내용은 아래의 링크에 있습니다.
탐색 알고리즘 - 1. 선형 탐색 / 2. 이진 탐색 알고리즘
이글은 코드잇 의 알고리즘 강의와 오픈소스 들을 참고하여 정리한 글입니다^^ 알고리즘 공부 방법 하나의 문제를 해결하는 방법에는 여러가지가 있다. 그 방법들을 찾아서 가장 좋은 방법을 찾
nittaku.tistory.com
반응형