무차별(무작위) 대입 Brute Force

/

모든 가능한 경우를 대입하여 문제를 해결하려는 방식

• (장점) 직관적, 명확, 확실한 답
• (단점) 비효율적
• 효율적인 알고리즘의 첫 시작을 위해 알아야 한다.

문제의 복잡성이나 해결 방법이 명확하지 않을 때, 보다 효율적인 알고리즘을 사용하기 어려운 경우에 적용한다. 그리고 문제의 크기가 크거나, 계산 비용이 높거나, 해결 가능한 다른 효율적인 방법이 있거나, 문제가 최적화 문제인 경우에는 사용 불가능하다.

예제 문제

• 카드 뭉치 최대 조합
• 빗물 트래킹
  
  

➲ 카드 뭉치 최대 조합

# 카드 뭉치 최대 조합
def max_product(left_cards, right_cards):
    # 처음에는 임시로 각 리스트의 첫 번째 요소의 곱으로 설정
    max_product = left_cards[0] * right_cards[0]
    for left in left_cards:
        for right in right_cards:
            max_product = max(max_product, left * right)   # 현재 최댓값, 지금 값 비교
    return max_product

# 가까운 매장 찾기
from math import sqrt

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

def closest_pair(coordinates):   # 가장 가까운 두 매장 찾기
    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]
            if distance(pair[0], pair[1]) > distance(store1, store2):
                pair = [store1, store2]
    return pair

➲ 빗물 트래킹

# 빗물 트래킹
def trapping_rain(buildings):
    total_rain = 0   # 총 담기는 빗물의 양
    for i in range(1, len(buildings) - 1):
        max_left = max(buildings[:i])
        max_right = max(buildings[i:])
        hight = min(max_left, max_right)
        total_rain += max(0, hight - buildings[i])
    return total_rain

🌟 개발 블로그 참고 🌟
알고리즘과 자료구조 살펴보기

코드잇 알고리즘패러다임