TIL | 알고리즘 기초 # 4

vel.Ash·2022년 4월 18일

이진탐색 재귀로 구현해보기

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    # start_index가 end_index보다 크면 some_list안에 element는 없다
    if start_index > end_index:
        return None
      
    # 범위의 중간 인덱스를 찾는다
    mid = (start_index + end_index) // 2
  
    # 이 인덱스의 값이 찾는 값인지 확인을 해준다
    if some_list[mid] == element:
        return mid

    # 찾는 항목이 중간 값보다 작으면 리스트 왼쪽을 탐색해준다
    if element < some_list[mid]:
        return binary_search(element, some_list, start_index, mid - 1)

    # 찾는 항목이 중간 값보다 크면 리스트 오른쪽을 탐색해준다
    else:
        return binary_search(element, some_list, mid + 1, end_index)     
        
        
# 테스트 코드 
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

0
None
2
1
4

Brute Force - 2

가능한 모든 방법을 다 시행하는 것

예제 2

가까운 매장 찾기

생각..
# 일단 하나 씩 들어가기 for문 사용 
# 중첩문 사용해야 할 거같애 왜냐면 모든 경우의 수 비교할거야 
# i j 사이의 거리 구하기 -> 리스트에 저장하기 
# 근데 매장 위치를 리턴해주니까 range() 사용 
# 계속 최솟값을 구해줘 if 문써서 전의 최소값 현재값 비교해서 i, j 저장하도록

# 제곱근 사용을 위한 sqrt 함수
from math import sqrt

# 두 매장의 직선 거리를 계산해 주는 함수
def distance(store1, store2):
    return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)

# 가장 가까운 두 매장을 찾아주는 함수
def closest_pair(coordinates):
    distance_list = []
    for i in range(len(coordinates)):
        for j in range(len(coordinates)):
            distance_vlaue = distance(coordinates[i], coordinates[j])
            if distance_vlaue != 0:
                distance_list.append(distance_vlaue)
        min_distance = min(distance_list)
        
    for i in range(len(coordinates)):
        for j in range(len(coordinates)):
            distance_vlaue = distance(coordinates[i], coordinates[j])
            if distance_vlaue == min_distance:
                n, m = i, j 
    result = [coordinates[m], coordinates[n]]
    return result
    

# 테스트
test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(test_coordinates))

[(2, 3), (3, 4)]

<모범답안>

# 제곱근 사용을 위한 sqrt 함수
from math import sqrt

# 두 매장의 직선 거리를 계산해 주는 함수
def distance(store1, store2):
    return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)

# 가장 가까운 두 매장을 찾아주는 함수
def closest_pair(coordinates):
    distance_list = []
    # 현재까지 본 가장 가까운 두 매장
    pair = [coordinates[0], coordinates[1]]
    for i in range(len(coordinates) - 1):
        for j in range(i + 1, len(coordinates)):
            store1, store2 = coordinates[i], coordinates[j]
            
            # 더 가까운 두 매장을 찾으면 pair 업데이트
            if distance(pair[0], pair[1]) > distance(store1, store2):
                pair = [store1, store2]
    return pair 

# 테스트
test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(test_coordinates))

예제 3

빗물 받기 계산

def trapping_rain(buildings):
    collect_rain = 0
    for i in range(1, len(buildings) - 1):
        # 왼쪽, 오른쪽 근처 가장 높은 길이
        max_left = max(buildings[:i])
        max_right = max(buildings[i:])
        
        # 빗물이 고일 수 있는 높이 
        able_collect = min(max_left, max_right)
        
        # 고여진 빗물의 높이 
        collect_rain += max(0, able_collect - buildings[i])
        
    return collect_rain
        
    
# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))