백준 [10815] 숫자 카드
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.
예제 입력 1
5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10
예제 출력 1
1 0 0 1 1 0 0 1
풀이의 문제점
상근이는 50만개의 카드를 가질 수 있다.
=> 카드 수 1 ~ 50만개
비교할 카드도 50만 개이다. => 비교 카드 수 1 ~ 50만개
여기까지 계산해도 단순 비교를 하다면 250000000000번의 연산이 필요하다.
파이썬에서 1초에 연산할 수 있는 횟수는 1000만에서 1억번의 연산이 가능하다.
대략 250초에서 2500초가 걸린다.
시간제한이 2초이므로 이 알고리즘으로 해답을 찾는 문제는 아니다.
그러므로 좀 더 효율적인 알고리즘이 필요하다.
풀이의 핵심 1
출력형식을 보니 비교할 카드가 있다, 없다를 판단해주면 좋을 듯하다.
그런데 어떻게?
자, 우리가 무언가를 탐색하는데 있어서 어떻게 생각하는지 생각해보자.
자, 이렇게 위에 10개의 숫자가 있고 나는 6가 있는지 없는지 알고 싶다.
즉 상근이가 가진 카드가 위에 있는 숫자, 비교할 숫자카드가 6인 셈이다.
우리는 왼쪽부터 오른쪽으로 훑으며, 6와 비슷한 모양이 있는지 판단할 것이다.
컴퓨터의 방식으로는 모두 다 하나씩 비교하는 방법이 될 수 있겠다.
이렇게 탐색대상이 10개, 20개가 된 경우 우리 인간은 이걸 빠르게 탐색할 수 있다.
하지만 100개만 되더라도 바로 머리가 지끈하다.
그래서 우리는 다른 방법을 생각한다.
내가 아는 모양으로 이 배열을 환원시켜 그 모양이 가지는 특징을 적용하는 것이다.
즉 새로운 시각을 얻을 수 있는 방법이다.
이 경우 그 모양은 삼각형 이 될 수 있다.
수의 분포는 선형적으로 커지기 때문에 우리는 삼각형모양을 떠올릴 수 있다.
원래 방금 저 수를 시각화하면 이렇다.
개수가 적을 때는 일일히 조사를 할 수 있지만 늘어나게 되면 이 방법은 힘이 든다.
그래서 이 분포를 정리하여 아는 모양으로 만든다.
이 상태에서 내가 6를 판단한다면
5근처에서 판단하고 그 주변에서 찾을 것이다.
즉, 양쪽의 대부분 값은 버릴 것이다.
어렵게 삼각형이라고 말했지만 사실 정렬을 하는 것이다.
상근이가 가진 카드 숫자를 오름차순, 내림차순으로 정렬하면 된다.
자. 그런데 버린다는 판단을 우리는 쉽게하지만 이걸 컴퓨터가 알아먹게 어떻게 말할 수 있을까?
아니 그전에 우리는 어떻게 양쪽을 쳐다도 안보고 바로 중간인 5로 접근할 수 있을까?
너무도 자연스러운 이 생각을 찬찬히 뜯어보자.
풀이의 핵심 2
자. 다시 생각해보면 우리는 섞여있는 카드에서는 일일히 조사해서 판단했다.
그런데 이걸 정렬하고, (시각화를 해보면) 삼각형 모양으로 바꾸니 일일히 조사하지 않고
바로 어디있는지 찾아냈다.
그렇다면 저 삼각형이 우리의 사고를 도와주고 있다 는 말이 된다.
자 그럼 삼각형이 우리를 어떻게 도와주고 있을까?
정렬을 하면 우리는 어떤 정보를 손쉽게 얻을 수 있을까?
답은 다음과 같다.
- 수의 분포, 즉 size를 알 수 있다.
- 중간을 비교한다.
좀 더 확실한 이해를 위해 1~10 말고 다른 수를 가져오겠다.
1~32에서 2의 제곱들이 흩어져 있는 것을
정렬해보면 다음과 같다.
여기서 내가 5를 찾고 싶다면 우리는 일단 삼각형의 큰 부분이 있을 때
반정도는 버리고 왼쪽에서 찾기를 시작할 것이다.
이런 식으로 말이다.
어떤 생각과정이 생략되었을까?
그럼 이 16이라는 녀석은 내가 원하는 6이랑 다르다!
그럼 6이 16보다 클까 작을까?
작다
그러니까 저 나뉘어진 도형에서 왼쪽에 일단 있겠네?
그래서 왼쪽을 택했다.
이 과정을 계속 반복한다.
정리
데이터를 정렬
이 과정은 데이터의 분포를 알아 낼 수 있다는 점에서 중요하다.
우리가 수의 사이즈를 알 수 있다는 것은 최댓값과 최솟값을 안다 는 것과 같은 말이다.
그렇다면 비율로 값을 유추할 수 있다는 강력한 도구 가 생긴다.
중간값과 비교한다.
중간값을 하는 이유는 컴퓨터의 특징을 이용하기 위함이다.
오른쪽에 값이 있냐 없냐, 혹은 왼쪽에 값이 있냐, 없냐 와 같은 두개의 질문중 하나만 선택한다면
다른 값은 자동적으로 정해진다. 이는 컴퓨터가 2진 연산을 하기 때문에 이 판단이 보다 직관적이다.
최댓값 혹은 최솟값을 업데이트 한다.
왼쪽에 있는지, 오른쪽에 있는지를 판단했다면 내가 바라볼 도형에만 집중한다.
마찬가지로 만약 오른쪽에 있다면 이번엔 최솟값을 업데이트한다.
이것을 최대한 수행하고 minimum이 maximum보다 커지게 될 때 프로그램을 종료한다.
이 부분은 코드를 다루면서 좀 더 추가해서 설명하겠다.
결론
결론적으로 이 방법은 우리가 고등학생 때 배운 중간값의 정리로 근을 유추하는 방법과 매우 유사하다.
또는 컴퓨터가 근을 구하는 방법(똑같은 얘기)과 똑같다.
또 컴퓨터가 무언가를 분류할 때 사용하는 지표중 정보엔트로피와 비슷하다.
결국 이 방법을 사용하게 되면 애초에 최대 50만 * 50만의 경우를 다 판단해야 되는 것에서
지수승의 개수만큼으로 판단하는 것으로 연산횟수가 줄어든다.
이것을 시간 복잡도 표현을 사용하게 되면
으로 감소했다.
앞의 n은 비교할 카드를 총 조사해야함을 의미하는 n이며,
뒤의 log는 상근이의 카드중 비교할 카드 한장이 있는지 없는지 판단할 때 걸리는 연산횟수를 의미한다.
결론적으로 log2를 사용한 표현은 단일 루프에서 컴퓨터가 할 수 있는 연산을 최적화 했을 때
얻을 수 있는 시간 복잡도 이다.
직관적으로 이 시간 복잡도에 해당하는 알고리즘을 만들기 위한 힌트는 반으로 나눈다에서 찾을 수 있겠다.
코드
input_number = int(input())
input_data = input()
input_data = input_data.split(' ')
input_data = list(map(int,input_data))
input_data.sort()
check_number = int(input())
check_data = input()
check_data = check_data.split(' ')
check_data = list(map(int,check_data))
for i in range(check_number):
answer = 0
left = 0
right = input_number - 1
mid = (left + right) // 2
while(left <= right):
if input_data[mid] == check_data[i]:
answer = 1
break
elif input_data[mid] < check_data[i]:
left = mid + 1
else:
right = mid - 1
mid = (left + right) // 2
print(answer,end = ' ')