[python_파이썬_Pass]백준_1920번_수찾기_이분탐색_풀이

공부하는허딩크 : https://www.youtube.com/live/YUFXMQL1DWY?feature=shared

 

 
<첫번째 시도 : 시간초과>
일단 딱 봐도 쉬운 문제였다. 간단한 for문과 if문으로 작성했는데 시간초과....

시간 복잡도

• 리스트 탐색에서 M_nums의 각 요소에 대해 N_nums를 순차적으로 탐색하기 때문에 시간 복잡도가 **O(M * N)**입니다.
• 만약 M과 N이 큰 경우, 시간 초과가 발생할 수 있습니다. 특히 입력 크기가 큰 경우(예: M, N이 100,000 이상), 탐색에 상당한 시간이 소요됩니다.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

# 시간초과

for i in M_nums:

    if i in N_nums:

        print(1)

    else:

        print(0)

 
<두번째 시도 : 맞았습니다.>
처음 공부할때 딕셔너리에서 해시를 통해서 찾기를 하면 속도가 빠르다는 걸 체감했다.
But, N_nums에 없는 요소가 있을 수 있기 때문에 try, except구문을 활용했다.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = {}

for i in N_nums:

    answer[i] = 1

   

for i in M_nums:

    try:

        if not answer[i]:

            print(0)

        else:

            print(answer[i])

    except:

        print(0)

 

해시(Hash)란?

• 해시는 데이터를 특정한 방식으로 변환하여 **고유한 키(key)**를 생성하는 알고리즘입니다.
• 파이썬의 딕셔너리는 내부적으로 해시 테이블이라는 자료구조를 사용하여 구현됩니다. 각 키는 해시 함수에 의해 해시 값으로 변환되며, 이 해시 값을 이용해 값을 저장하거나 검색합니다.

딕셔너리에서의 동작 방식

1. 저장: 딕셔너리에 데이터를 저장할 때, 주어진 키는 해시 함수에 의해 해시 값으로 변환됩니다. 이 해시 값은 해시 테이블에서 특정 위치(버킷)를 결정하며, 이 위치에 해당하는 값을 저장합니다.위 코드를 실행할 때 i는 해시 함수에 의해 해시 값으로 변환되고, 그 위치에 1을 저장합니다.
2. python
   코드 복사
   answer[i] = 1
3. 검색: 딕셔너리에서 키를 통해 값을 검색할 때도 동일하게 키가 해시 함수에 의해 해시 값으로 변환되며, 그 해시 값에 해당하는 위치에서 값을 빠르게 찾을 수 있습니다.i in answer는 i의 해시 값을 사용해 딕셔너리에서 해당 키가 존재하는지 빠르게 확인할 수 있습니다.
4. python
   코드 복사
   if i in answer:

해시의 장점

• 빠른 검색: 해시 구조 덕분에 평균적으로 O(1) 시간 복잡도로 데이터를 저장하고 검색할 수 있습니다. 리스트와 같은 순차 탐색과 달리, 데이터의 양이 많아져도 검색 속도가 크게 느려지지 않습니다.

해시의 단점

• 충돌 문제: 두 개의 다른 키가 같은 해시 값을 가질 경우(해시 충돌), 이를 처리하기 위한 추가적인 작업이 필요합니다. 하지만 파이썬 딕셔너리는 이러한 충돌을 효과적으로 처리하는 기법(예: 체이닝, 개방 주소법 등)을 사용하여 성능 저하를 최소화합니다.

따라서 딕셔너리를 사용하는 것은 해시 테이블을 활용하여 데이터를 빠르게 검색할 수 있는 장점이 있는 방법입니다.
 
<다른 사람 풀이 참고>
get()함수는 딕셔너리에서 값을 안전하게 가져오기 위한 메서드이다. 위에 내가 풀이를 한 것처럼 딕셔너리에서 키를 사용해 값을 가져올 때, 해당 키가 존재하지 않으면 KeyError가 발생하는데, get()함수는 이러한 에러를 방지하면거 기본값을 설정 할 수 있다는 장점이 있다.
 
※ dict.get(key, default_value) : default_value는 선택사항으로 키가 없으면 반환값을 None으로 한다.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = {}

for i in N_nums:

    answer[i] = 1

for i in M_nums:

    print(answer.get(i, 0))

 

<추가 학습 : 이진탐색으로 작성시 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

#[1, 2, 3, 4, 5]

def binary(arr, m):

    arr.sort()

    start, end = 0, len(arr) - 1

   

    while start <= end:

        mid = (start + end) // 2

        if arr[mid] == m:

            return True

        elif arr[mid] > m:

            end = mid - 1

        else:

            start = mid + 1

    return False

           

for i in M_nums:

    if binary(N_nums, i):

        print(1)

    else:

        print(0)

#목표값이 N_nums에 있는지 확인 -> 범위를 줄여서 확인 필요

 

sort를 함수 내부가 아니라 외부로 빼니까 통과됨.

 

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

N_nums.sort()

#[1, 2, 3, 4, 5]

def binary(arr, m):

    start, end = 0, len(arr) - 1

   

    while start <= end:

        mid = (start + end) // 2

        if arr[mid] == m:

            return True

        elif arr[mid] > m:

            end = mid - 1

        else:

            start = mid + 1

    return False

           

for i in M_nums:

    if binary(N_nums, i):

        print(1)

    else:

        print(0)

#목표값이 N_nums에 있는지 확인 -> 범위를 줄여서 확인 필요

 

<Chat GPT 문의 : 해시를 이용한 방법과 이진탐색을 이용한 방법 비교>

1. 첫 번째 코드: 이진 탐색 방식 (Binary Search)

이 코드는 이진 탐색 알고리즘을 사용하여, M_nums에 있는 각 숫자가 N_nums 리스트에 존재하는지 확인합니다.

시간 복잡도:

• N_nums.sort()는 O(N log N) 시간 복잡도를 가집니다. 이는 N_nums 리스트를 정렬하는 데 걸리는 시간입니다.
• binary() 함수는 이진 탐색을 사용하므로 각 탐색의 시간 복잡도는 **O(log N)**입니다. 따라서, M_nums의 각 원소에 대해 이진 탐색을 수행하므로 총 탐색 시간은 **O(M log N)**입니다.

전체 시간 복잡도:

• 정렬: O(N log N)
• 이진 탐색을 통한 탐색: O(M log N)
• 총 시간 복잡도는 **O(N log N + M log N)**입니다.

효율성:

• 이 코드는 이진 탐색을 사용하여 탐색 속도가 빠르고, 특히 N_nums가 크더라도 정렬 후 빠르게 탐색할 수 있다는 장점이 있습니다.
• 다만, 정렬에 걸리는 시간이 추가되므로, N_nums의 크기가 매우 크다면 그에 대한 추가 비용이 발생합니다.

2. 두 번째 코드: 해시 테이블 (Dictionary) 방식

두 번째 코드는 N_nums 리스트의 값을 딕셔너리로 저장하고, M_nums의 각 값을 딕셔너리에서 찾는 방식으로 동작합니다.

시간 복잡도:

• 딕셔너리를 생성하는 데 드는 시간은 **O(N)**입니다. 각 숫자를 딕셔너리에 추가하는 시간은 상수 시간 **O(1)**이므로, N_nums의 길이만큼 반복하더라도 **O(N)**입니다.
• answer.get(i, 0)로 딕셔너리에서 값을 찾는 작업은 상수 시간 **O(1)**입니다. 따라서, M_nums의 각 숫자에 대해 탐색을 하므로 탐색 시간은 **O(M)**입니다.

전체 시간 복잡도:

• 딕셔너리 생성: O(N)
• 딕셔너리를 통한 탐색: O(M)
• 총 시간 복잡도는 **O(N + M)**입니다.

효율성:

• 딕셔너리 방식은 정렬이 필요 없으며, 숫자를 딕셔너리에 추가하고 찾는 작업 모두 상수 시간에 이루어집니다.
• 따라서 이 방식은 매우 빠르고, N과 M의 크기가 매우 커질수록 첫 번째 방법보다 훨씬 효율적입니다.

결론

• 첫 번째 코드 (이진 탐색): 시간 복잡도는 O(N log N + M log N). 이진 탐색은 빠르지만, N_nums를 정렬하는 추가 비용이 발생합니다.
• 두 번째 코드 (딕셔너리 사용): 시간 복잡도는 **O(N + M)**로, 첫 번째 방법보다 더 효율적입니다. N_nums를 정렬할 필요가 없고 딕셔너리의 빠른 조회 속도를 활용합니다.

따라서 두 번째 코드가 더 효율적입니다, 특히 데이터 크기가 클 경우 딕셔너리 방식을 사용하는 것이 더 좋은 선택입니다.

 

<다른 사람 코드 참고 : 이상적인 코드>

import sys

input = sys.stdin.readline

N = int(input())

N_nums = set(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

for i in M_nums:

    print(int(i in N_nums))