[알고리즘] 문제6 - Greedy Algorithm

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다.

 

Greedy Algorithm

- 당장 눈 앞에 보이는 최적의 선택을 하는 방식

- 최적의 답이 필요 없거나, 다른 알고리즘이 너무 느릴때 사용

- 최적 부분 구조가 있고, 탐욕적 선택 속성이 있다면 그리디 알고리즘이 최적의 솔루션을 보장함

 

장점

- 간단하고 빠르다

 

단점

- 최적의 답이 보장되지 않는다

---

 

 1. 최소 동전으로 거슬러 주기

 

 조건 

- 함수명 : min_coin_count

- 매개변수명 : value(거슬러 줘야하는 총약), coin_list(동전리스트)

- 최소 동전 갯수 반환

---

풀이

def min_coin_count(value, coin_list):
    # 누적 동전 개수
    count = 0

    # coin_list의 값들을 큰 순서대로 본다
    for coin in sorted(coin_list, reverse=True):
        # 현재 동전으로 몇 개 거슬러 줄 수 있는지 확인한다
        count += (value // coin)

        # 잔액을 계산한다
        value %= coin

    return count

# 테스트
default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))
print(min_coin_count(32590, default_coin_list))

 

---

 

 

2. 최대 곱 구하기

 

 조건 

- 함수명 : max_product

- 매개변수명 : card_lists(카드 리스트들)

- 카드 리스트들에서 만들 수 있는 최대 곱 반환

---

풀이

def max_product(card_lists):
    # 누적된 곱을 저장하는 변수
    product = 1

    # 반복문을 돌면서 카드 뭉치를 하나씩 본다
    for card_list in card_lists:
        # product에 각 뭉치의 최댓값을 곱해 준다
        product *= max(card_list)

    return product


# 테스트
test_cards1 = [[1, 6, 5], [4, 2, 3]]
print(max_product(test_cards1))

test_cards2 = [[9, 7, 8], [9, 2, 3], [9, 8, 1], [2, 8, 3], [1, 3, 6], [7, 7, 4]]
print(max_product(test_cards2))

test_cards3 = [[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5], [5, 2, 3], [3, 2, 1]]
print(max_product(test_cards3))

test_cards4 = [[5, 5, 5], [4, 3, 5], [1, 1, 1], [9, 8, 3], [2, 8, 4], [5, 7, 4]]
print(max_product(test_cards4))

 

 

 

풀이1 (공간최적화 X)

def fib_tab(n):
    # 이미 계산된 피보나치 수를 담는 리스트
    fib_table = [0, 1, 1]

    # n번째 피보나치 수까지 리스트를 하나씩 채워 나간다
    for i in range(3, n + 1):
        fib_table.append(fib_table[i - 1] + fib_table[i - 2])

    # 피보나치 n번째 수를 리턴한다
    return fib_table[n]

# 테스트
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))

 

풀이2 (공간최적화 O)

def fib_optimized(n):
    current = 1
    previous = 0

    for i in range(1, n):
        current, previous = current + previous, current

    return current


# 테스트
print(fib_optimized(16))
print(fib_optimized(53))
print(fib_optimized(213))