[알고리즘 패러다임] 다이나믹 프로그래밍 (Dynamic Programming) - 2

guava·2021년 10월 5일

알고리즘 코드잇

알고리즘의 정석

목록 보기

11/13

코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.

이전 포스트에서는 다이나믹 프로그래밍과 기법을 알아보았다.(Memoization, Tabulation)
이번 포스트에서는 각 기법의 장단점을 비교해보고 좀더 심도있는 문제를 풀며 정리해보자.

8. Memoization vs Tabulation

공통점

Memoization, Tabulation은 둘 다 중복되는 문제의 비효율을 제거한다.

차이점

Memoization은 재귀함수, Tabulation은 반복문을 사용한다.
재귀 호출이 발생하면 Call Stack이 쌓인다. Call Stack의 용량이 제한적이라면 Tabulation이 적합할 수 있다.
Tabulation은 처음부터 모두 계산한다. 필요없는 것도 계산할 수 있다. Memoization은 하향식 접근을 하며 필요한 계산만 수행한다.

9. Dynamic Programming 공간최적화

Tabulation을 통해 피보나치 수열 문제를 개선하면 시간복잡도, 공간복잡도가 모두O(n)이 된다.
fib(20)을 풀기 위해서는 fib(19)와 fib(18)만 알면 된다. 하지만 Tabulation을 이용하면 모든 피보나치의 답을 저장해두게 된다.
리스트 대신 가장 최근 값만 저장하는 변수 두개를 활용해보자.
- 가장 최근값인 current, 그 직전값인 previous이 있다.
- 다음 피보나치 값은 current(previous + current)이고, 기존의 current값이 previous에 저장된다.

모든 값을 저장할 필요가 없다면 공간 최적화를 하자.

10. 피보나치 수열 공간 최적화

문제

n번째 피보나치 수를 계산하기 위해서는 가장 최근에 계산한 두 값만 알면 된다. 공간복잡도 O(1)로 fib_optimized함수를 작성하라.

def fib_optimized(n):
    # 코드를 작성하세요. 

print(fib_optimized(1))    # 1을 출력
print(fib_optimized(2))    # 1을 출력
print(fib_optimized(3))    # 2을 출력
print(fib_optimized(4))    # 3을 출력
print(fib_optimized(5))    # 5을 출력

풀이

앞서 설명한 Dynamic Programming 공간 최적화를 참고한다.

코드

def fib_optimized(n):
    # 코드를 작성하세요. 
    previous, current = 0, 1
    for i in range(1, n):
        previous, current = current, previous + current
    return current

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

# 콘솔 출력
987
53316291173
146178119651438213260386312206974243796773058

11. 새콤달콤 장사 분석

솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌는데요...

가능한 최대 수익을 리턴시켜 주는 함수 max_profit을 작성해 보세요. max_profit은 파라미터로 개수별 가격이 정리되어 있는 리스트 price_list와 판매할 새꼼달꼼 개수 count를 받습니다.

예를 들어 price_list가 [100, 400, 800, 900, 1000]이라면,

새꼼달꼼 1개에 100원
새꼼달꼼 2개에 400원
새꼼달꼼 3개에 800원
새꼼달꼼 4개에 900원
새꼼달꼼 5개에 1000원

이렇게 가격이 책정된 건데요. 만약 오늘 솔희가 새꼼달꼼 5개를 판매한다면 최대로 얼마를 벌 수 있을까요?

한 친구에게 3개 팔고 다른 친구에게 2개를 팔면, 800 + 400을 해서 총 1200원의 수익을 낼 수 있겠죠.

def max_profit(price_list, count):
    # 코드를 작성하세요.

# 테스트
print(max_profit([100, 400, 800, 900, 1000], 5))

문제 분석

최적 부분 구조가 존재하는가? - 존재한다. 5개를 파는것의 최대 수익은 다음과 같이 나눌 수 있다.
1. 5개를 한 명에게 팔 때의 가격
2. 4개를 팔아서 가능한 최대 수익 + 1개를 팔아서 가능한 최대 수익
3. 3개를 팔아서 가능한 최대 수익 + 2개를 팔아서 가능한 최대 수익
  
  3가지 경우를 모두 알아야 한다. 부분 문제의 답을 이용해 기존 문제의 답을 구할 수 있기 때문에 이 문제에는 최적 부분 구조가 있다.
중복되는 부분 문제는 존재하는가? - 존재한다.
이 문제를 Dynamic Programming으로 해결할 수 있는가? - 해결 가능하다.

⇒ 최적 부분 구조와 중복되는 부분 문제가 있기 때문에 해결 가능하다.

12. 새콤달콤 장사 Memoization

문제

가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 Memoization 방식으로 작성해 보세요. max_profit_memo는 파라미터 세 개를 받습니다.

price_list: 개수별 가격이 정리되어 있는 리스트
count: 판매할 새꼼달꼼 개수
cache: 개수별 최대 수익이 저장되어 있는 사전

예를 들어 price_list가 [0, 100, 400, 800, 900, 1000]이라면,

새꼼달꼼 0개에 0원
새꼼달꼼 1개에 100원
새꼼달꼼 2개에 400원
새꼼달꼼 3개에 800원
새꼼달꼼 4개에 900원
새꼼달꼼 5개에 1000원

이렇게 가격이 책정된 건데요. 만약 솔희가 새꼼달꼼 5개를 판매한다면 최대로 얼마를 벌 수 있을까요?

한 친구에게 3개 팔고 다른 친구에게 2개를 팔면, 800 + 400을 해서 총 1200원의 수익을 낼 수 있겠죠.

def max_profit_memo(price_list, count, cache):
    # 코드를 작성하세요.

    
def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)

# 테스트
print(max_profit([0, 100, 400, 800, 900, 1000], 5))
print(max_profit([0, 100, 400, 800, 900, 1000], 10))
print(max_profit([0, 100, 400, 800, 900, 1000, 1400, 1600, 2100, 2200], 9))

# 콘솔 출력
1200
2500
2400

풀이

base case를 생각해본다.
memoization이니까 cache에 솔루션이 있는지 확인하는 절차가 먼저일 것이다.

recursive case를 생각해보자. 판매가 가능한 조합을 생각해보는게 중요하다.

"""
가능한 조합
2개
2개, 0개
1개, 1개

3개
3개, 0개
2개, 1개

4개
4개, 0개
3개, 1개
2개, 2개

5개
5개, 0개
4개, 1개
3개, 2개
"""

코드

def max_profit_memo(price_list, count, cache):
    # base case
    if count < 2:
        cache[count] = price_list[count]
        return cache[count]
    
    # cache에 저장된 값이 있으면 반환
    if count in cache:
        return cache[count]
        
    # recursive case
    # price_list에 값이 존재하면 일단 profit에 저장
    if count < len(price_list):
        profit = price_list[count]
    else:
        profit = 0
        
    # 가능한 조합을 순회하며 profit을 갱신한다.
    for i in range(1, count//2+1):
        profit = max(profit,
            max_profit_memo(price_list, count-i, cache) + max_profit_memo(price_list, i, cache)
        )
    cache[count] = profit
    return cache[count]

    
def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)

# 테스트
print(max_profit([0, 100, 400, 800, 900, 1000], 5))
print(max_profit([0, 100, 400, 800, 900, 1000], 10))
print(max_profit([0, 100, 400, 800, 900, 1000, 1400, 1600, 2100, 2200], 9))

# 콘솔 출력
1200
2500
2400

13. 새콤달콤 장사 Tabulation

가능한 최대 수익을 리턴시켜 주는 함수 max_profit을 Tabulation 방식으로 작성해 보세요. max_profit은 파라미터 두 개를 받습니다.

price_list: 개수별 가격이 정리되어 있는 리스트
count: 판매할 새꼼달꼼 개수

예를 들어 price_list가 [0, 100, 400, 800, 900, 1000]이라면,

새꼼달꼼 0개에 0원
새꼼달꼼 1개에 100원
새꼼달꼼 2개에 400원
새꼼달꼼 3개에 800원
새꼼달꼼 4개에 900원
새꼼달꼼 5개에 1000원

이렇게 가격이 책정된 건데요. 만약 솔희가 새꼼달꼼 5개를 판매한다면 최대로 얼마를 벌 수 있을까요?

한 친구에게 3개 팔고 다른 친구에게 2개를 팔면, 800 + 400을 해서 총 1200원의 수익을 낼 수 있겠죠.

def max_profit(price_list, count):
    # 코드를 작성하세요. 

# 테스트
print(max_profit([0, 200, 600, 900, 1200, 2000], 5))
print(max_profit([0, 300, 600, 700, 1100, 1400], 8))
print(max_profit([0, 100, 200, 400, 600, 900, 1200, 1300, 1500, 1800], 9))

# 콘솔 출력
2000
2400
1800

풀이

def max_profit(price_list, count):
    # 0개, 1개 가격 저장해두기
    table = price_list[:2] 
    
    # 2개 이상일 때 테이블에 기록
    for i in range(2, count+1):
        # price_list안에 있는 가격을 일단 profit에 저장
        if count < len(price_list):
            profit = price_list[i]
        else:
            profit = 0
            
        # i개를 팔수 있는 가능한 조합을 비교해서 더 큰 값을 profit에 저장
        for j in range(1, i//2+1): 
            profit = max(profit, table[j]+table[i-j])
        table.append(profit)
    return table[count]

# 테스트
print(max_profit([0, 200, 600, 900, 1200, 2000], 5))
print(max_profit([0, 300, 600, 700, 1100, 1400], 8))
print(max_profit([0, 100, 200, 400, 600, 900, 1200, 1300, 1500, 1800], 9))

# 콘솔 출력
2000
2400
1800

guava

이전 포스트

[알고리즘 패러다임] 다이나믹 프로그래밍 (Dynamic Programming) - 1

다음 포스트

[알고리즘 패러다임] 다이나믹 프로그래밍 (Dynamic Programming) - 2

알고리즘의 정석

8. Memoization vs Tabulation

공통점

차이점

9. Dynamic Programming 공간최적화

10. 피보나치 수열 공간 최적화

문제

풀이

코드

11. 새콤달콤 장사 분석

문제 분석

12. 새콤달콤 장사 Memoization

문제

풀이

코드

13. 새콤달콤 장사 Tabulation

풀이

[알고리즘 패러다임] 다이나믹 프로그래밍 (Dynamic Programming) - 1

[알고리즘 패러다임] 그리디 알고리즘(Greedy Algorithm) - 1

0개의 댓글