[python] 1920. 수 찾기

• 문제 

---

 

• 잘못된 풀이

import sys

# 시간초과
N = int(input())
num_list = list(map(int, sys.stdin.readline().split()))

M = int(input())
check_list = list(map(int, sys.stdin.readline().split()))

for i in check_list:
    if i in num_list:
        print("1")
    else:
        print("0")

 

해당 문제는 주어진 수가 리스트 안에 있는지 여부를 판단하는 문제이다.

나는 문제를 딱 보자마자 바로 in을 써서 푸는 방법을 떠올렸고, 실제로 in을 사용해서 문제를 해결하면 쉽게 풀리는 문제이다.

 

하지만, 오늘도 시간초과 ...

문제를 보고 바로 떠오르는 해결방법이라도, 코드를 작성하기 전에 먼저 시간복잡도를 따져보고

더 낮은 시간복잡도의 방법을 선택하는 것이 옳은 문제해결방법임을 깨달았다.

(물론 시간복잡도가 낮다고 해서 절대적으로 올바른 풀이방법은 아니다.)

 

in을 통해 for문으로 문제를 풀었을 때는, 매 for문마다 해당 숫자가 리스트 안에 있는지 리스트 전체를 확인/비교해야 한다. 

하지만 매번 전체 리스트를 확인하는 것이 아니라, 절반으로 나누어 해당 숫자가 포함된 범위만 가지고 판단하는 방법도 있다.

바로 이진 탐색 ! 

 

이진탐색이란 ?
데이터가 정렬되어 있는 상태(배열)에서 특정한 값을 찾아내는 알고리즘이다. 방법은 다음 설명과 같다. 먼저, 배열의 중앙값을 찾는다. 중앙값을 기준으로, 내가 찾고자 하는 값이 왼쪽 범위에 해당하는지 / 오른쪽 범위에 해당하는지 / 혹은 그 값(중앙값)인지 확인한다. 만약 찾고자 하는 값이 중앙값보다 작으면 왼쪽 범위만 보고 값을 찾고, 찾고자 하는 값이 중앙값보다 크면 오른쪽 범위만 보고 값을 찾는다. 즉, 배열 안에서 특정한 값을 찾을 때 배열 전체를 보는 것이 아니라, 중앙값을 기준으로 절반만 본다는 것이다. 배열 안에서 값을 찾을 때까지 반복한다.

 

---

 

• 올바른 풀이 1 (반복문으로 푼 경우)

import sys

N = int(input())
num_list = sorted(list(map(int, sys.stdin.readline().split())))

M = int(input())
check_list = list(map(int, sys.stdin.readline().split()))

# 이진탐색 반복문
def binarySearch(i):
    low = 0
    high = len(num_list) - 1

    while low <= high:
        mid = int((low + high) / 2)

        if num_list[mid] == i:  # 중간값
            return 1
        elif num_list[mid] > i:  # 작은값
            high = mid - 1
        else:
            low = mid + 1
    return 0

for i in check_list:
    num = binarySearch(i)
    print(num)

 

위의 코드는 이진 탐색을 while의 반복문으로 푼 경우이다.

while을 통해 내가 찾고자 하는 값을 찾을 때까지 돈다. (low < high인 경우안에서)

 

 

 

• 올바른 풀이 2 (재귀로 푼 경우)

import sys

N = int(input())
num_list = sorted(list(map(int, sys.stdin.readline().split())))

M = int(input())
check_list = list(map(int, sys.stdin.readline().split()))

# 이진탐색 재귀함수
def binarySearch(i, low, high):
    if low > high:
        return 0
    mid = int((low+high)/2)
    if num_list[mid] == i:
        return 1
    elif num_list[mid] > i:
        return binarySearch(i, low, mid-1)
    else:
        return binarySearch(i, mid+1, high)

for i in check_list:
    low = 0
    high = len(num_list)-1

    num = binarySearch(i, low, high)
    print(num)

 

위의 코드는 이진 탐색을 재귀로 분 경우이다.

while처럼 해당 숫자를 찾을 때까지 반복문을 도는 방법이 아니라, recursive로 low와 high를 달리하여 함수를 도는 것이다.

 

 

이진 탐색으로 문제를 해결할 때의 시간 복잡도는, O(logN)이 된다.

설명) N 크기의 배열을 이진 탐색하면 N, N/2, N/4, N/8, ..., 1으로 실행된다. 

실행된 탐색의 횟수가 시간 복잡도가 될 것이고, 그 값을 k라고 한다면 k는 N에 대해 이렇게 나타낼 수 있다. 

1에 2를 k번 곱하면 N이 된다 → 2^k = N → K = logN → O(logN)