실전 코딩 테스트-이진 탐색 알고리즘

본 자료와 관련 영상 컨텐츠는 저작권법 제25조 2항에 의해 보호를 받습니다. 본 컨텐츠 및 컨텐츠 일부 문구 등을 외부에 공개하거나, 요약해서 게시하지 말아주세요.

<a href='www.fun-coding.org'>잔재미코딩(www.fun-coding.org) Dave Lee</a>

실전 코딩 테스트 - 탐색 알고리즘

본 문제는 각 자료구조/알고리즘을 보다 실전 문제와 연결하여 연습함으로써, 해당 자료구조/알고리즘 이해도와 숙련도를 높이기 위함입니다. 따라서, 해당 문제에서 나오는 핵심 컨셉의 구현에만 초점을 맞춤니다.

1. https://www.acmicpc.net/problem/1920

왜 다음 코드가 좋지 않을까요?

실제로 다음과 같이 작성하면, 시간 제한에 걸립니다.

N = int(input())N_list = list(map(int, input().split())M = int(input())M_list = list(map(int, input().split())

# 여러 차례 테스트를 위해, input 구문으로 직접 입력을 받지 않고, 그대로 실제 테스트 예제 입력을 변수로 넣었습니다.N = 5N_list = [4, 1, 5, 2, 3]M = 5M_list = [1, 3, 7, 9, 5]

for item in M_list:    if item in N_list:        print(1)    else:        print(0)

1
1
0
0
1

시간복잡도 개선 코드

이진 탐색 알고리즘 기반 코드 개선

# 여러 차례 테스트를 위해, input 구문으로 직접 입력을 받지 않고, 그대로 실제 테스트 예제 입력을 변수로 넣었습니다.N = 5N_list = [4, 1, 5, 2, 3]M = 5M_list = [1, 3, 7, 9, 5]

N_list.sort()def binary_search(data, search):    if len(data) == 0:        return 0    elif len(data) == 1:        if data[0] == search:            return 1        else:            return 0    medium = len(data) // 2    if search == data[medium]:        return 1    else:        if search > data[medium]:            return binary_search(data[medium+1:], search)        else:            return binary_search(data[:medium], search)for item in M_list:    print(binary_search(N_list, item))

1
0
0
0
1

참고 코드

• 테스트시 input() 실행 후, 정확히 값을 입력하지 않을 경우, 해당 코드가 실행중인 상태가 되므로, 더이상 다른 코드가 동작하지 않습니다.
• 이 부분이 정확히 이해가 안가는 경우, 다음 코드 실행 보다는, 위의 코드를 테스트해보시면 좋을 것 같습니다.
• 해당 부분의 테스트와, 다른 코드가 실행되지 않는 상황에 대한 당황스러움을 방지하고자 해당 코드는 실행이 안되는 Raw NBConvert 타입으로 바꿔놓았습니다.

본 자료와 관련 영상 컨텐츠는 저작권법 제25조 2항에 의해 보호를 받습니다. 본 컨텐츠 및 컨텐츠 일부 문구 등을 외부에 공개하거나, 요약해서 게시하지 말아주세요.

<a href='www.fun-coding.org'>잔재미코딩(www.fun-coding.org) Dave Lee</a>