1. 공부한 내용

문제1 - 99 클럽 - 징검다리:

[ 이진 탐색 ] ⇒ O(logN)

: Binary Search란 배열 내부의 데이터가 정렬되어 있을 때, 빠르게 데이터를 찾을 수 있는 탐색 법이다. 구현 방법의 핵심은 시작점, 끝점, 중간점을 설정하여 탐색하는 것이다.

⇒ 빈출 유형이니, 암기하는 것이 좋다!!!

1) 재귀 함수로 이진 탐색 구현하기

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end)//2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 target 값이 작은 경우
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    # 중간점의 값보다 target 값이 큰 경우
    else:
        return binary_search(array, target, mid+1, end)
    
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
    print('원소 존재 X')
else:
    print(result+1)

2) 반복문으로 이진 탐색 구현하기

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end)//2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우
        else:
            start = mid + 1
    return None

# n(원소의 갯수)과 target을 입력 받기
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)
if result == None:
    print('원소 존재 X')
else:
    print(result + 1)

2. 오늘의 회고

오늘의 문제는 이진 탐색 문제였으나, 초기 접근을 이진 탐색으로 하지 않으면 시간 복잡도 에러가 발생하는 유형이었다. 다행히 문제 풀이 초기에 유사한 아이디어가 생각나서 방향은 잘 맞췄으나, 오랜만에 풀었던 이진 탐색 문제라 잘 기억이 나지 않았었다.. 다양한 유형을 반복적으로 상기시켜주는 것이 좋을 듯 하다.

연습만이 살길22222!!!