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
[오답] → 시간초과
다른 블로그들을 참고해보니 "이진 탐색(이진 검색)" 으로 풀어야 시간초과가 나지 않는다는 것을 알았다. 나는 알고리즘 수업시간에 배운 <19 이기적 정보처리기사 실기 기본서> p.1-281~283을 참고하여 이 문제를 풀었다.
[정답]
1. 리스트 A의 길이인 N과 검색 대상인 리스트 A를 오름차순 정렬하여 정의한다.
2. 리스트 num_list의 길이인 M과 찾고자 하는 대상인 리스트 num_list를 정의한다.
3. 이진 탐색을 진행한다.
1) 검색 대상 리스트 데이터의 하한 인덱스 변수인 L과 검색 대상 리스트 데이터의 상한 인덱스 변수인 H를 정의한다.
2) 만약 L>H일 경우 찾고자 하는 대상이 없다는 의미이므로 '0'을 출력한다.
3) L과 H의 중간 인덱스 변수인 M을 정의한다.
4) 만약 A[M]==i 라면 찾고자 하는 대상을 찾았으므로 '1'을 출력한다.
5) A[M]>i 라면 즉 찾고자 하는 대상이 중간 인덱스의 값보다 작다면 중간 인덱스의 값보다 작은 수들과 비교해야 하므로 H=M-1을 해주고 다시 while문을 돈다.
6) 5번과 같이 A[M]<i라면 즉 찾고자 하는 대상이 중간 인덱스의 값보다 크다면 중간 인덱스의 값보다 큰 수들과 비교해야 하므로 L=M+1을 해주고 다시 while문을 돈다.
[참고]
이진탐색의 원리
https://terms.naver.com/entry.nhn?docId=2270440&cid=51173&categoryId=51173
이진 탐색
이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다. 예를들어 비유하면, 가나다순으로 정렬되어 있는 전화번호부에서 임의의 사람에 대한 전화번호를 찾는 경우다.
terms.naver.com
'알고리즘 공부 > 백준 > Python3' 카테고리의 다른 글
| [백준 파이썬] #2480: 주사위 세개 (0) | 2021.01.09 |
|---|---|
| [백준 파이썬] #10815: 숫자 카드 (0) | 2021.01.07 |
| [백준 파이썬] #2530: 인공지능 시계 (0) | 2021.01.05 |
| [백준 파이썬] #3046: R2 (0) | 2021.01.05 |
| [백준 파이썬] #1225: 이상한 곱셈 (0) | 2021.01.05 |
