문제
느낀점
처음에 선형탐색으로 in을 사용해서 풀었을 땐 풀리긴 했으나 시간초과가 떴다.
그래서 자료구조 책을 보면서 검색을 더 빠르게 할 수 있는 알고리즘이 없나 살펴보았다. 검색 알고리즘 중 두 번째 챕터였던 이진 검색을 통해 더 빠르게 검색 할 수 있다는 걸 알게 되고, 책의 알고리즘을 참고해서 코드를 작성해보았다. 해당 코드를 아래 써보겠지만, 다른 분들의 코드를 보고 더 가독성 있게 코드를 만들어서 이진탐색을 해보았다.
또한 코테에서 으레 만들라는 solution 함수를 만드는 방식으로 이진탐색 풀이를 진행해보았다. 처음으로 파이썬에서 함수와 그 바깥에 for문을 이용하는 방식을 결합하여 문제를 풀어보니 매우 뿌듯했다 :)
책에서 한 번 공부했던 이진탐색이지만, 역시 코드는 직접 문제를 보고 활용해보아야 비로소 내 것이 될 수 있는 것 같다. Do It! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)을 절반 가량 읽었는데 속도를 붙여서 1월 안에 1회독을 끝내고 2월엔 2회독을 하면서 코테 문제에 유연하게 배운 알고리즘을 적용하고 싶다.
개념
이진탐색
원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘.
중요한 건 검색 대상인 배열이 오름차순이나 내림차순으로 배열되어 있어야만 한다는 것이다.
이 부분을 놓쳐서 처음에 코드가 이상하게 나왔다.
책에선 a[pc]라는 리스트에서 key라는 찾아야 하는 값이 있었다. 그러나 이 문제는 책과는 다르게 A라는 리스트에서 B라는 리스트의 원소가 있는지 찾아야만 했다. 응용해야 할 부분은 이진탐색을 하는 함수 부분은 그대로 두되, B라는 리스트의 원소를 for문을 돌려서 key로 원소를 하나씩 넣어줘야 했다.
아래는 책에 나와있는 예제 코드이다.
from typing import Any, Sequence
def bin_search(a: Sequence, key: Any) -> int:
"""시퀀스 a에서 key와 일치하는 원소를 이진 검색"""
pl = 0 # 검색 범위 맨 앞 원소의 인덱스
pr = len(a) - 1 # 검색 범위 맨 끝 원소의 인덱스
while True:
pc = (pl + pr) // 2 # 중앙 원소의 인덱스
if a[pc] == key:
return pc # 검색 성공
elif a[pc] < key:
pl = pc + 1 # 검색 범위를 뒤쪽의 절반으로 좁힘
else:
pr = pc - 1 # 검색 범위를 앞쪽의 절반으로 좁힘
if pl > pr:
break
return -1 # 검색 실패시간초과 풀이 (선형탐색, in 활용)
N = int(input())
A = list(map(int,input().split()))
M = int(input())
B = list(map(int,input().split()))
for i in range(len(A)) :
if B[i] in A : print("1")
else : print("0")이진탐색 풀이
from typing import Sequence
N = int(input())
A = list(map(int,input().split()))
A.sort() # 검색 대상인 A 를 오름차순 정렬 (필수)
M = int(input())
B = list(map(int,input().split()))
def bin_search(A:Sequence, target:int) -> bool :
left = 0
right = N - 1
while left <= right: # left > right이면 검색범위가 더이상 없음
pc = (left + right) // 2
if A[pc] == target :
return True
elif A[pc] < target :
left = pc + 1
else :
right = pc - 1
for i in range(M) :
if bin_search(A, B[i]) :
print("1")
else :
print("0")Refer.
https://tmdrl5779.tistory.com/115
Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)
