[백준] 11501번 문제풀이

그리드 알고리즘의 특성

그리드 알고리즘(탐욕 알고리즘)은 문제 해결 방식 중 하나로, 매 순간 가장 좋아 보이는 선택을 하는 방법입니다. 이 방법의 핵심은 두 가지 주요 특성에 기반합니다.

1. 탐욕 선택 속성 (Greedy Choice Property): 각 단계에서의 최적의 선택이 전체적인 해결책에 대해서도 최적임을 의미합니다.
2. 최적 부분 구조 (Optimal Substructure): 문제의 최적 해결책이 그 부분 문제의 최적 해결책으로부터 구성될 수 있음을 의미합니다.

백준 11501번 문제 풀이

이 문제는 날짜별 주가가 주어졌을 때, 최대 이익을 계산하는 문제입니다. 이 문제를 풀기 위해 다음과 같은 탐욕적 접근 방식을 사용했습니다:

• 미래의 최대 주가를 알고 있을 때, 그 시점에 주식을 판매하는 것이 최적의 선택입니다.
• 이 접근 방식은 각 날짜별로 독립적인 최적의 선택을 하여 전체적으로도 최대 이익을 낼 수 있습니다.

아래는 파이썬으로 구현한 코드입니다

def calculate_max_profit_boj(prices):
    max_profit = 0  # 최대 이익 초기화
    max_future_price = 0  # 미래의 최대 주가 초기화

    # 뒤에서부터 주가를 검사합니다.
    for price in reversed(prices):
        if price > max_future_price:
            max_future_price = price  # 새로운 최대 주가 업데이트
        max_profit += max_future_price - price  # 이익 계산 및 추가

    return max_profit

# 테스트 케이스 예시
test_cases_boj = [
    [10, 7, 6],
    [3, 5, 9],
    [1, 1, 3, 1, 2]
]

# 각 테스트 케이스에 대한 최대 이익 계산
results_boj = [calculate_max_profit_boj(prices) for prices in test_cases_boj]

문제풀이에 대한 의문점

• 그리드 알고리즘은 현재 상태에서 최적의 답을 선택하는 건데, 문제풀이는 미래 상태를 알고, 최적의 답을 구한다. 이것도 그리드 알고리즘인가?
• 문제는 '미래의 주가를 알고 있다'를 가정하고 있다. 미래의 정보를 활용하여 현재 최적의 선택을 결정하는 게 가능하다.