알고리즘 패러다임: Brute Force

• 알고리즘 패러다임: 다양한 문제를 해결할 때, 알고리즘을 만드는 접근법을 묶어서 카테고라이징함. 한 문제에도 다양한 솔루션이 존재함. 여러 알고리즘 패러다임으로 한 문제를 풀 수 있다.
  실마리를 찾아가봅시다

무차별 대입 공격 Brute-Force Attack

e.g. 비밀번호 4자리를 0000 부터 9999까지 가능한 모든 경우의 수 모두 대입해봄 -> 가장 순진한 접근법

카드뭉치 최대 조합

내 답변

def max_product(left_cards, right_cards):
    new_list = [ ] 
    for left in left_cards:
        for right in right_cards:
            all_list = left * right
            new_list.append(all_list)
    return max(new_list)       

해답

def max_product(left_cards, right_cards):
    # 현재까지 최댓값을 담기 위한 변수
    # 처음에는 임시로 -1로 설정
    max_product = -1
    
    # 가능한 모든 조합을 보기 위한 중첩 반복문
    for left in left_cards:
        for right in right_cards:
            # 현재까지의 최댓값 값과 지금 보고 있는 곱을 비교해서 더 큰 값을 최댓값 변수에 담아준다
            max_product = max(max_product, left * right)

    # 찾은 최댓값을 리턴한다            
    return max_product
    
print(max_product([1, 6, 5], [4, 2, 3]))
print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
print(max_product([-1, -7, 3], [-4, 3, 6]))

answer:
24
32
28

장점

직관적이고 명확함, 모든 경우의 수 따지기 때문에 답을 확실히 찾을 수 있음

단점

input이 클수록 비효율적이게 됨

결론

input 이 크지 않으면 굳이 더 효율적인 알고리즘 쓰지 않아도 괜찮다.
인풋이 클 때는 효율적인 알고리즘 찾기의 출발점으로서 Brute Force를 사용하면서 접근해야함.