Brute Force 알고리즘 이란?

완전탐색

• 모든 가능한 경우를 다 접근하여 결과 값 도출 한다.

장점

• 직관적이고 명확하다.
• 답을 확실하게 찾을 수 있다.

단점

• input 값이 커질 경우 시간이 오래 걸린다.

---

Brute Force 알고리즘 예제

카드 뭉치 최대 조합 구하기

문제

카드 두 뭉치가 있습니다. 왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶다. 어떻게 하면 가장 큰 곱을 구할 수 있을까?

1. 함수 max_product는 리스트 left_cards와 리스트 right_cards를 파라미터로 받습니다.

2. left_cards는 왼쪽 카드 뭉치의 숫자들, right_cards는 오른쪽 카드 뭉치 숫자들이 담겨 있고, max_product는 left_cards에서 카드 하나와 right_cards에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴합니다.

접근

• 리스트 left_cards 와 right_cards의 각각의 값을 곱해야 하니 이중 for문을 사용하자.
• result 변수에 left * right 값을 저장한다.
• result 값이 이미 저장 되어 있는 max_number 변수 값 보다 크면 max_number = result
• 알고리즘 개념을 공부중이니 내장 함수 사용을 하지 않고 코드를 짜보려 했다.
  ➡️ 최대값 도출 max() 함수 대신 if문 사용

code

def max_product(left_cards, right_cards):
    max_number = 0
    for left in left_cards:
        for right in right_cards:
            result = left * right
            if max_number < result:
                max_number = result
    return max_number


print(max_product([1, 6, 5, 2], [4, 2, 3, 1]))
print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
print(max_product([-1, -7, 3], [-4, 3, 6]))

결과 값

• 

---

참고

코드잇 - 알고리즘의 정석 강의 예제
https://www.codeit.kr/courses/algorithms