[Baekjoon, Python] 1920번: 수 찾기

도입

백준 단계별 풀기에서 이분탐색 첫 번째 문제이다. 

백준 1920번 문제, 입력, 출력

---

백준 1920번 입출력 예제 1

---

풀이

1. 이분탐색이 무엇인가! 쉽게 얘기해 보자면 인덱스값을 나타내는 변수를 하나 두고, 반씩 쪼개면서 찾는 방법이다.  0~99까지의 정수를 가지는 크기 100의 배열이 있다. 오름차순으로 정렬이 되어있다. 인덱스 0에 0이 인덱스 1에 1이 있는 그런 배열이다. 여기서 62를 찾으려고 한다. 기존의 경우, for문으로 0부터 차례대로 찾는다면 62번을 for문 안을 반복 한다.

 이분탐색에서, mid라는 변수에 "배열의 길이/2"로 초기화하고 한번씩 수행할 때마다 mid=mid/2를 수행한다고 해보자. (여러 추가적인 것들 다 배제하고) 그렇다면 처음 mid값:50, 찾는 수(62)는 50보다 크니, 다음 51(mid+1)~99(right)사이의 숫자에서 mid를 찾는다 mid값:75, 찾는 수(62)는 75보다 작다. 다음 51(left)~75(mid)사이의 숫자에서 mid를 찾는다. mid값:62가 곧 찾는 수가 된다. 3번만에 찾았다. 

 

2. 문제는, N개의 정수가 들어있는 집합 A, M개의 정수가 들어있는 집합 B가 있다면, B의 요소들이 A에 포함되어 있는지를 묻는다. 

 

3. 여기서 set이 아닌 list를 사용하면, 시간초과가 뜰 것이다. 자세한 사항은 파이썬의 자료형에 따른 시간복잡도를 참고하자.

---

코드

from sys import stdin, stdout

num_n = stdin.readline()
N = set(stdin.readline().split())
num_m = stdin.readline()
M = stdin.readline().split()

for l in M:
    stdout.write('1\n') if l in N else stdout.write('0\n')

 

---

마무리

이제부터의 백준 알고리즘은, 파이썬으로 풀려고 한다. 이번에 풀어보니 확실히 접근은 쉬운데, 공간복잡도에서 메모리를 비교적 많이 잡아 먹는 것을 알 수 있었다. 기존의 C++은 기껏해야 4000정도였는데, 이번에 파이썬으로 풀어본 이분탐색은 4만이 훌쩍 넘었다. 하지만, 코딩테스트를 준비하는데 있어서는 크게 상관이 없을 것이다. 

---