좌충우돌 IT이야기

● 문제 출처 Site

[코드]

def Count(num):
    lt = 0
    rt = len(a)-1
    cnt = 0
    while lt <= rt:
        mid = (lt+rt)//2
        if num == a[mid]:
            cnt = 1
            return cnt
        elif num < a[mid]:
            rt = mid - 1
        else:
            lt = mid + 1
    return cnt


n = int(input())
a = list(map(int, input().split()))

m = int(input())
b = list(map(int, input().split()))
a.sort()
for x in b:
    if Count(x) > 0:
        print('1')
    else:
        print('0')

[느낀 점]

애초에 문제 분류를 이분 탐색 으로 설정해서 풀었기 때문에, 생각하는데는 많이 어렵진 않았다. 하지만 정확하게 문제를 이해하는게 좀 힘들었다. 아직 문제에 대한 이해력이 많이 부족한것 같다. 그리고 과연 이 문제가 이분 탐색이라고 안나왔다면 내가 풀 수 있었을까...? 라는 의구심도 든다. 

또한, 코드를 옮겨서 리뷰를 해보니 변수 선언에 좀 더 신중해야 겠다는 생각이 든다.

[설명]

이진 탐색은 찾고자하는 값을 중앙값을 기준으로 찾는 알고리즘입니다. 해당 알고리즘을 사용하려면 중요한 선행작업 필요합니다.

바로 순차정렬입니다. 찾고자하는 값이 x가 중앙값 보다 작다면 왼쪽을 탐색, 크다면 오른쪽을 탐색하기 때문입니다. 그러므로 이때 정렬이 되어 있지 않다면 우리가 원하는 값이 아닌 다른 값이 나오게 될것입니다.

만약 x = 3 이라면, 먼저 정렬된 배열의 중앙값을 찾습니다. 그 후 찾고자 하는 값은 2이므로 왼쪽을 탐색합니다.

2를 찾아왔지만, 원하는 값은 2보다 크므로 오른쪽을 탐색합니다.

[파이썬 코드]

a = [7, 8, 9, 1, 2, 3, 4, 5, 6]
a.sort(reverse=False)
low = 0
high = len(a)-1
while low <= high:
    p = (high + low) // 2
    if a[p] == k:
        print(p+1)
        break
    elif a[p] < k:
        low = p + 1
    else:
        high = p - 1