[백준] 10815번 : 숫자 카드 - 파이썬

아이디어 : 딕셔너리, 해시테이블, 이분탐색

자료구조 - 딕셔너리

: 키(key)와 값(value)의 쌍으로 이루어진 자료구조

- 키를 기준으로 중복된 값을 가질 수 없음

- 키와 값 모두 어떤 자료형이든 사용이 가능함

딕셔너리는 데이터베이스에서 사용되는 해시 테이블(hash table) 구조를 기반으로 구현되며, 따라서 매우 빠르게 조회와 추가, 삭제가 가능함

 

※ 딕셔너리 생성, 값 조회, 키-값 쌍 추가, 키-값 쌍 제거, .keys(), .values(), .items()

my_dict = {'apple': 1, 'banana': 2, 'orange': 3}

# 딕셔너리 키를 사용하여 값 조회
print(my_dict['apple'])  # 1

# 딕셔너리 새로운 키-값 쌍 추가
my_dict['melon'] = 4
print(my_dict)  # {'apple': 1, 'banana': 2, 'orange': 3, 'melon': 4}

# 딕셔너리 키-값 쌍 제거
del my_dict['banana']
print(my_dict)  # {'apple': 1, 'orange': 3, 'melon': 4}

# 딕셔너리 키의 리스트 조회
print(my_dict.keys())  # dict_keys(['apple', 'orange', 'melon'])

# 딕셔너리 값의 리스트 조회
print(my_dict.values())  # dict_values([1, 3, 4])

# 딕셔너리 키-값 쌍의 리스트 조회
print(my_dict.items())  # dict_items([('apple', 1), ('orange', 3), ('melon', 4)])

# 딕셔너리 비우기
my_dict.clear()
print(my_dict)  # {}

 

※ in : 해당 Key가 딕셔너리 안에 있는지 조사하기

my_dict = {'apple': 1, 'banana': 2, 'orange': 3}

if 'apple' in my_dict:
    print("Yes")

 

ChatGPT : 파이썬으로 이분탐색 알고리즘에 대해 알려줘

이분 탐색(binary search) 알고리즘은 정렬된 배열에서 특정 값을 찾는 데에 사용되는 알고리즘입니다. 이 알고리즘은 배열의 중간 값을 선택하고, 찾고자 하는 값과 비교하여 다음에 탐색할 위치를 결정하는 과정을 반복하면서 값을 찾아갑니다.

def binary_search(arr, x):
    """
    arr: 정렬된 리스트
    x: 찾고자 하는 값
    """
    low = 0
    high = len(arr) - 1
    mid = 0
    
    while low <= high:
        mid = (high + low) // 2
        
        # 중간값이 찾고자 하는 값인 경우
        if arr[mid] == x:
            return mid
        
        # 중간값이 찾고자 하는 값보다 큰 경우, 왼쪽 반 탐색
        elif arr[mid] > x:
            high = mid - 1
        
        # 중간값이 찾고자 하는 값보다 작은 경우, 오른쪽 반 탐색
        else:
            low = mid + 1
    
    # 찾고자 하는 값이 없는 경우
    return -1

위 코드에서 low는 배열의 맨 처음 인덱스를, high는 배열의 맨 마지막 인덱스를 나타냅니다. mid는 low와 high의 중간값을 가리키는 변수입니다. 이분 탐색 알고리즘의 핵심은 mid를 기준으로 배열을 둘로 나누고, 찾고자 하는 값이 mid보다 작은지 큰지에 따라 다음에 탐색할 위치를 결정하는 것입니다.

while 루프에서는 low가 high보다 작거나 같을 때까지 반복합니다. 이는 배열을 계속해서 둘로 나누어가면서, 결국 찾고자 하는 값이 배열에서 없어지게 되는 경우를 처리하기 위한 조건입니다. mid가 찾고자 하는 값과 같으면 해당 인덱스를 반환하고, mid가 찾고자 하는 값보다 크면 배열의 왼쪽 반을 탐색하고, 작으면 오른쪽 반을 탐색합니다.

만약 찾고자 하는 값이 배열에 없으면 -1을 반환합니다.

 

나의 답안

답안 1 - 딕셔너리 사용

import sys

input = sys.stdin.readline
N = int(input().strip())

list_N = list(map(int, input().split()))
dict_N = {}
for n in list_N:
    dict_N[n] = True

M = int(input().strip())
list_M = list(map(int, input().split()))

for m in list_M:
    if m in dict_N:
        print("1")
    else:
        print("0")

 

답안 2 - 이분탐색 사용

import sys

input = sys.stdin.readline
N = int(input().strip())
list_N = list(map(int, input().split()))

M = int(input().strip())
list_M = list(map(int, input().split()))

list_N.sort()

def binary_search(arr, x):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left+right)//2
        if arr[mid] == x:
            return 1
        
        elif arr[mid] < x:
            left = mid + 1
        
        elif arr[mid] > x:
            right = mid -1

    return 0

for m in list_M:
    print(binary_search(list_N, m), end=' ')

 

딕셔너리 사용 알고리즘(위에 것)이 이분 탐색 사용 알고리즘(아래 것)보다 더 빠르다. (메모리는 더 사용한다)

 

추가

list.sort() : 리스트의 항목들을 오름차순으로 정렬하는 메소드

my_list = [3, 2, 1]

# 오름차순 정렬
my_list.sort()
print(my_list)  # [1, 2, 3]

# 내림차순 정렬
my_list.sort(reverse=True)
print(my_list)  # [3, 2, 1]