[BOJ 1920][백준 1920번] 수 찾기 (파이썬 풀이)

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

1920번: 수 찾기

🤔 문제 설명 및 입출력

---

 

 

✍ 접근 방법

---

문제는 N개의 수로 이루어진 리스트 A를 주고, M개의 수로 이루어진 리스트 B(가칭)을 줍니다. 그리고 B의 각 요소들이 A에 포함되어있는지를 확인해서, 존재한다면 1을 출력하고, 그렇지 않다면 0을 출력합니다.

 

보다시피 구현해야할 기능은 매우 간단합니다. 그냥 검색만 잘하면 끝!!!!

그렇다면, 리스트 B의 요소들에 대해 리스트 A의 요소들과 일일이 비교하면 될까요???

 

당연히 아닙니다. 입력을 보면 알겠지만, N의 최대값은 100,000이고,  M의 최대값은 100,000입니다. 그럼 최악의 경우 이 한문제를 풀기 위해서 100,000 * 100,000 번의 비교를 시행해야합니다. (A의 모든 요소가 B의 마지막 요소와 일치한다고 가정한다면) 

 

아무리 생각해봐도 절대 효율적인 방법은 아닙니다.

 

이 시점에서 "에이 아무리 그래도 이렇게 극단적인 경우가 있겠어??" 라고 생각하신다면 그런 극단적인 일이 비일비재 한 곳이 프로그래밍의 세계라고 말씀드리고 싶습니다. 그리고, 진짜진짜진짜 적은 확률로 일어나는 일까지 온전하게 처리할 수 있는 코드를 만드는 것이 참된 개발자입니다.

 

여러분들께 로봇 가정부가 하나 있다고 해봅시다. 이 로봇은 진짜 밥도 잘하고, 청소도 잘하고 못하는게 없는 완전 만능로봇인데, 개발자가 소프트웨어 설계를 잘못하는 바람에 1년에 한 번 오류가 날 수 있습니다. 오류가 나면 로봇은 완전히 미쳐버려 초가삼간 다 때려부수고 여러분들까지 때려부수려는 미친 로봇이 됩니다.

 

이런 로봇, 쓰시겠습니까???

 

같은 맥락입니다. 완전 오류가 없는 로봇이 베스트이지만, 오류가 난다면 적어도 10분간 동작을 멈추는 수준의 마이너 한 수준이여야할 것입니다. 그렇기 때문에 개발자들은 PS에 있어 항상 최악의 경우를 상정하는 것입니다. 이런걸 워낙 많이 하다보니, 이런 복잡도 문제를 빅-오 표기법이라는 것으로 수식화 하기에 이릅니다.

 

근데 여기서 빅오 표기법까지 꺼내는건 배보다 배꼽이 더 커지는 수준이므로, 그럼 이 문제를 어떻게 해결해야하는지를 간략히 설명하고 풀이에 들어가겠습니다.

 

이런 큰 자료에서 검색할 때에는, "이진탐색"이라는 방법을 사용합니다.

 

 

이진탐색은 찾고자 하는 값과 자료의 가운데에 있는 항목의 값과 비교하면서, 검색의 범위를 줄여나가는 탐색방법입니다. 쉽게 말하자면, 큰 책에서 특정 페이지를 찾기위해 먼저 가운데를 열어보았을때, 그 페이지가 내가 찾는 페이지보다 작다면 책의 뒷부분을 찾아보고, 내가 찾는 페이지 보다 크다면 책의 앞부분을 찾아보는 것과 동일한 로직입니다.

 

로직을 순서에 따라 기술하자면 아래와 같습니다.

 

1. 자료의 중앙에 있는 원소를 고른다
2. 중앙 원소의 값과 찾고자 하는 목표값을 비교한다
3. 목표값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로운 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
4. 찾고자 하는 값을 찾을 때까지 1~3의 과정을 반복한다.

 

이진탐색은 제대로 수행된다면 엄청나게 빠른 속도를 보이지만, 이진탐색은 요소들이 정렬된 리스트에서만 사용될 수 있습니다.

 

이진탐색은 검색범위를 조절할때, 현재 값보다 뒤에 있는 값은 현재 값보다 크고, 앞에 있는 값은 현재 값보다 작다는 것을 전제로 하기 때문입니다.

 

이진탐색은 반복문 / 재귀함수로 구현할 수 있는데, 이번 문제는 재귀함수를 이용해서 풀어보겠습니다.

 

 

👨‍💻 소스 코드

---

• 파이썬

def bin_search(start:int, end: int, lst:list,target_value:int):
    # start == end 인 경우에도 정답이 될 수 있다. --> 딱 중간에서 만났을때
    if start > end:
        return 0

    else:
        mid = (start+end)//2
        mid_value = lst[mid]
        if mid_value == target_value:
            return 1
        # 재귀로 돌리면 이미 검사한 mid는(idx)는 검사 범위에 안들어가게 해야한다
        # return 값을 재귀의 결과로 받아야한다. 함수가 스택에서 빠져나가면서 위로 return 결과를 들고 오기 때문.
        # 그렇지 않다면 그대로 검색 결과가 그대로 증발한다.
        elif mid_value > target_value:
            return bin_search(start,mid-1,lst,target_value)
        elif mid_value < target_value:
            return bin_search(mid+1,end,lst,target_value)


N = int(input())
num_lst = list(map(int,input().split()))
M = int(input())
target_num_lst = list(map(int,input().split()))

num_lst.sort()

for num in target_num_lst:
    print(bin_search(0,N-1,num_lst,num))

 

여기서 핵심은 새로운 탐색을 시작할때마다 시작 인덱스와 끝 인덱스가 mid ∓ 1로 바뀐다는 점입니다. 만약에 mid를 그대로 시작/끝 인덱스로 사용하게 된다면, 무한루프에 빠질 우려가 있기 때문입니다.  이 점에 유의하여 코드를 작성합시다.

 

 

 

🔥 강평

---

이진탐색 문제를 처음 푸신다면, 확실히 엄청 헷갈리실겁니다. 저도 골치를 꽤나 썩혔던 기억이 납니다. 이진탐색 문제는 직접 그림을 그려가면서 전체 흐름을 따라가시는게 많은 도움이 될 껍니다.

 

여담으로, 요즘 블로그에 글이 뜸해서 빠르게 글 하나만 쓰자~ 라는 생각으로 푼 문제인데, 빅오 표기법 얘기하다가 분량이 엄청 길어져버렸네요..

 

빅오 표기법에 대해서는 다음에 알고리즘 일반 탭에서 다루도록 하겠습니다.