[Baekjoon] 백준 알고리즘: 1920번 - 수 찾기

문제

www.acmicpc.net/problem/1920

1920번: 수 찾기

내가 생각했던 풀이과정

 

1) 이진탐색을 사용하려면 정렬되야 하기 때문에, 처음 정렬을 한다

2) 시작을 start, 끝을 end로 index를 설정해주고, 찾아야할 숫자는 in 함수를 통해 반복문을 돈다.

3) 시작이 끝보다 작을 때까지 반복하며 이진 탐색을 위해 중간지점을 찾는다

중간지점이 타겟이라면 1을 return하고

중간지점의 값보다 타겟이 작을 경우 중간지점을 -1하고

타겟보다 클 경우 중간 지점을 +1 한다

찾을 숫자가 있을 경우 타겟에 걸리기 때문에 1을 return 해주고, 없을 경우 0을 return 해준다.

 

나의 풀이

N = int(input())
list_N = list(map(int, input().split()))
M = int(input())
list_M = list(map(int, input().split()))

list_N.sort()

for i in list_M:
    start = 0 
    end = N - 1
    target = i
    answer = 0
    while (start <= end):
        mid = (start + end) // 2
        if list_N[mid] == target:
            answer = 1
            break
        elif target < list_N[mid]:
            end = mid - 1
        else:
            start = mid + 1
    print(answer)

다른 사람의 풀이

from sys import stdin, stdout
n = stdin.readline()
N = sorted(map(int,stdin.readline().split()))
m = stdin.readline()
M = map(int, stdin.readline().split())

def binary(l, N, start, end):
    if start > end:
        return 0
    m = (start+end)//2
    if l == N[m]:
        return 1
    elif l < N[m]:
        return binary(l, N, start, m-1)
    else:
        return binary(l, N, m+1, end)

for l in M:
    start = 0
    end = len(N)-1
    print(binary(l,N,start,end))

이분 탐색에는 반복문을 사용할 수도 있으나 재귀문을 이용하여 푸는 방식도 있습니다. 

다른 분은 재귀함수를 이용하여 풀이를 하셨습니다

1) 이분 탐색을 위해서 N을 정렬시킵니다.

2) 시작과 끝 지점의 index를 지정합니다.

3) 시작 인덱스와 끝 인덱스를 사용해서 중간 지점의 인덱스를 구합니다.

4) 중간 지점의 값과 element를 비교합니다.

• 동일한 값이면 찾았다!
• 값이 크다 => 중간보다 윗부분에서 탐색
• 값이 작다 => 중간보다 작은 부분에서 탐색
• 위 과정을 확인할 리스트가 없을 때까지 계속해서 반복한다.

5) 전체 리스트에서 확인이 불가능하면 없는 것으로 판별

 

새로 알게된 점, 확인해야할 점

1. 이분탐색

 

Binary Search Algorithm

- 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘

- 모든 값을 순회해야 하는 일반적인 Search보다 더 빠르다는 장점이 있음

- 중앙값을 찾는 값에 비교

-> (중앙값) > (찾는 값) : 중앙 값 기준으로 왼쪽(작은 부분)을 탐색

-> (중앙값) < (찾는 값) : 중앙 값 기준으로 오른쪽(큰 부분)을 탐색

 

 

Binary Search Process

- left를 0으로 초기화, right를 검색하는 리스트(배열)의 마지막 원소의 인덱스로 초기화

- mid 변수를 (left+right)/2로 설정하며 계속해서 탐색

- left > right가 되는 순간 탐색이 종료되고 그전에 해당 값을 찾으면 종료

 

반복문을 이용하는 방법

m_list.sort()
left = 0 
right = length-1

while left<=right:
    mid = (left+right)//2
    if m_list[mid] == target:
        print(mid+1)
        break
    elif m_list[mid]>target:
        right = mid-1
    else :
        left = mid+1

재귀함수를 이용하는 방법

def binarySearch(array, target, left, right):
    middle_idx = (left+right)//2
    print(middle_idx)
    middle = array[middle_idx]
    if target == middle:
        print('answer {}'.format(middle_idx))
    elif middle > target:
        binarySearch(array, target,left,middle_idx-1)
    elif middle < target:
        binarySearch(array, target,middle_idx+1,right)
    else: 
        return False