BOJ 10815번 숫자 카드

10815번: 숫자 카드

 

해당 숫자가 존재하는지 탐색하면 되는 문제이다.

하지만 숫자의 개수가 매우 많기 때문에 선형 탐색으로는 시간 초과를 받게 된다.

 

그렇다면 더 빠른 탐색 알고리즘을 사용하면 되는데 대표적으로 이진 탐색 알고리즘을 이용할 수 있다.

이진 탐색에 대하여 잘 모른다면 아래의 더보기 링크를 확인하자.

알고리즘 : 이진 탐색 (=이분 탐색, binary search)

 

이진 탐색을 진행하기 위해서는 데이터가 정렬되어 있어야 한다.

그중 O(n^2) 형태의 정렬 알고리즘을 사용하기에는 양이 조금 많다.

정렬 알고리즘에 대하여 잘 모른다면 정렬 알고리즘에 대해 먼저 찾아보자

정렬 '버블', '선택', '삽입' 정렬 추가 예정

정렬 '퀵' 정렬 추가 예정

 

정렬 '병합', '힙' 정렬 추가 예정

 

정렬 후, 이진 탐색을 진행하기만 하면 풀리는 문제이므로 추가적인 설명은 생략하겠다.

 

 

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지