[Python] 백준, 10815(이진 탐색)

프로그래머스 알고리즘 기초 강의를 완강한 후, 백준 온라인 저지로 넘어와 각 알고리즘의 문항들을 풀고 있다.

아직까진 프로그래머스 level2 문항들에 비해 비교적 쉬운 난이도의 문제들만 보이는데 점차 어려워질 것 같다.

​

탐색 알고리즘부터 시작해서 힙까지, 당분간은 백준 문항들 위주로 업로드할 것 같다.

​

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

 

# PYTHON CODE (1)

import sys
 
N = int(sys.stdin.readline())
list1 = list(map(int,sys.stdin.readline().split()))
M = int(sys.stdin.readline())
list2 = list(map(int,sys.stdin.readline().split()))
 
list1.sort()
 
def binary_search(pl,pr,seq: list, key: int):
 
    if pl > pr:
        return print('0', end = ' ')
 
    pc = (pl + pr)//2
    if seq[pc] == key:
        return print('1', end = ' ')
    elif seq[pc] > key:
        binary_search(pl,pc - 1, seq, key)
    else:
        binary_search(pc + 1, pr, seq, key)
 
for i in list2:
    binary_search(0,N-1,list1,i)

 

 

# PYTHON CODE (2)

import sys
 
N = int(sys.stdin.readline())
list1 = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
list2 = list(map(int, sys.stdin.readline().split()))
 
list1.sort()
 
 
def binary_search(seq: list, key: int):
    pl, pr = 0, N - 1
 
    while pl <= pr:
        pc = (pl + pr) // 2
 
        if seq[pc] == key:
            return print('1', end=' ')
        elif seq[pc] > key:
            pr = pc - 1
        else:
            pl = pc + 1
 
    return print('0', end=' ')
 
for i in list2:
    binary_search(list1, i)

재귀와 비재귀를 이용해 이진 탐색을 두가지 코드로 나타내었다.

 

문제를 맞은 사람의 풀이 중에 set함수를 이용하여 중복값을 제거해준 경우와, 이진 탐색 대신에 'in'함수를 이용하여 푼 경우를 봤는데 속도에서 차이가 있는 것 같아 조금 허무했다.

​

in 보다 이진탐색의 속도가 느리다면 굳이 탐색 알고리즘을 사용하는 이유가 없지 않나라는 생각이 든다.

​

매번 python에서 제공해주는 idle에서 코딩 연습을 진행하다가 pycharm 을 설치해 사용해봤는데, 아직 적응이 안되어 너무 어렵게 느껴진다.

인프런에 pycharm 사용법에 대한 강의가 있던데, 고민을 좀 해봐야겠다.

 

네이버 블로그에 코딩 공부를 업로드 중이었는데, 코드가 길어질수록 제한이 생겨 html 입력이 비교적 쉬운 티스토리로 둥지를 옮겼다. 

 

1일 1업로드를 기대하며...