[알고리즘 일기] 8. 카드 뭉치 최대 조합

문제 08. (2021-05-08)

​

카드 뭉치 최대 조합

카드 두 뭉치가 있습니다. 왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 나온 두 수의 곱 중 가장 큰 값을 구하시오.

​

​

​

​

❧ 테스트 셋

def max_product(left_cards, right_cards):
    # Code

# Test
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]))

---

❧ 출력 예시

24
32
28

---

❧ 정답

Try 1

def max_product(left_cards, right_cards):
    max_value = left_cards[0] * right_cards[0]
    for i in range(len(left_cards)):
        for j in range(len(right_cards)):
            compare_value = left_cards[i] * right_cards[j]
            if max_value < compare_value:
                max_value = compare_value
    return max_value

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]))

1️⃣ 구조적이지만 파이썬의 이점, 키워드를 사용하지 않아 코드가 간결하지 않음

​

​

Try 2

def max_product(left_cards, right_cards):
    max_value = left_cards[0] * right_cards[0]
    for i in left_cards:
        for j in right_cards:
            max_value = max(max_value, i * j)
    return max_value
    
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]))

1️⃣ Brute-Force-Attack(무차별 대입 공격) 알고리즘 패러다임

2️⃣ 가장 순진한 알고리즘 접근법

3️⃣ 중첩 반복문 사용 → 시간 복잡도 : O(mn)

​