Index로 상태 공간 정의하기

문제

 

2662번: 기업투자

---

재정의

두 가지 제약 조건이 존재한다.

• 정해진 투자액수만큼 투자 한다.
• 한 기업에는 한 번만 투자할 수 있다.

금액의 조합을 정해야 하고, 기업의 조합도 정해야 한다.

완전 탐색을 활용한다.

 

---

비 효율적인 상태공간 정의

완전 탐색을 해야하는 문제이다.

상태 공간을 기업의 개수, 남은 금액으로 단순하게 정의 했다.

그렇게 되면 다음과 같이 코드가 구성 된다.

다음 코드의 문제점이 무엇인지 생각 해 보자...

def get_max_profit() -> List[int]:
    def dfs(cnt: int, money: int) -> None:
        nonlocal max_profit, now_profit, result

        if money <= 0\
                or cnt <= 0:
            if now_profit > max_profit:
                max_profit = now_profit
                result = choice[:]
            return
        
        for i in range(1, money + 1):
            for j in range(m):
                if choice[j]:
                    continue

                now_profit += value_list[i][j]
                choice[j] = i

                dfs(cnt - 1, money - i)
                
                choice[j] = 0
                now_profit -= value_list[i][j]

비 효율적 상태공간으로 인해 문제가 발생한다.

1. 어느 기업을 선택했는지 추가 상태가 필요하다.
   단순하게 기업의 개수만 세리기 때문에, choice란 배열을 만들어서
   상태를 관리해야하는 문제가 생긴다.
   
   
2. DP를 활용하기 어렵다.
   조합을 만드는 과정에서 상태 공간의 중복이 많이 발생한다.
   DP를 사용해야 한다는 것을 의미한다.
   
   cnt, money로는 상태를 표현할 수 없으므로,
   cnt, visit, money로 상태공간을 정의하게 된다.
   3차원 dp를 사용해야 하는 문제가 발생한다.

---

효율적인 상태공간 정의

cnt를 사용한 이유는, 기업을 다 고려했는지 확인하기 위함이였다.

visit를 사용한 이유는, 기업을  사용했는지 확인하기 위함이였다.

인덱스를 활용하면 이를 변수 하나로 집약시킬 수 있다.

 

company_idx라는 변수를 활용하면, company_idx 이후의 회사만 고려한다

이는, 이전 회사들을 사용할 수 없음을 의미 하므로,

기업을 중복 사용할 일도 없고, idx가 company의 수와 같아지면 모두를 고려하기 때문이다.

 

기존 cnt, visit, money의 3차원 상태공간에서 idx, money의 2차원 상태공간으로 줄어들었다.

2차원 DP는 충분히 할만하다.

---

상태 공간을 확장하며 푸는 방식 (Tabulation)

아래와 같은 배낭 알고리즘이 상태 공간을 확장하며 푸는 방식이다.

중복 선택을 할 수 없기 때문에 a1을 골랐을 때의 상태공간을 구성한다.

그리고 a2를 골랐을 때의 상태공간을 구성한다. 단, a2의 상태공간을 구성할 때는 a1의 공간과 상호작용한다.

이 방식을 통해 모든 요소를 고려하고, 선택을 한 번씩만 했을 때의 상태공간을 구할 수 있다.

for i in range(1, n + 1):
        for j in range(capacity + 1):
            # 현재 물건을 가방에 넣을 수 있는 경우
            if weights[i - 1] <= j:
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])
            else:
                # 현재 물건을 가방에 넣을 수 없는 경우
                dp[i][j] = dp[i - 1][j]

우리는 위의 템플릿으로만 풀 수는 없다.

우리는 뽑을 수 있다, 없다의 2지 선다가 아니다.

뽑을 수 있는 것이 여러 개이기 때문에, for문을 추가해서 아래와 같이 구성한다.

for i in range(1, m+1):
    for j in range(1, n+1):
        dp[i][j] = dp[i-1][j]
        for k in range(1, j+1):
            dp[i][j] = max(dp[i][j], values[k][i] + dp[i-1][j-k])

---

상태 공간을 부분 문제로 푸는 방식 (Memorization)

재귀는 문제를 해결하기 위해 부분 문제로 분할을 한다.

그렇기에 부분 문제를 일관성있게 만들게 되는데, 이에서 중복되는 값을 활용하는 것이다.

1 ~ n까지의 합을 구하는 함수를 재귀로 만들게 되면,
n + (1 ~ (n-1)), 1 + (2 ~ n)의 두 가지 형태로 쪼갤 수 있다.

재귀함수로 만들려면 전자의 방식을 사용해야 한다. 1 ~ n까지라는 일관성을 유지하기 때문이다.

부분 문제의 일관성을 위해서 다음과 같이 재정의 한다.

invest(company_idx: int, capacity: int) -> int
돈이 capacity만큼 남았을 때, company_idx 이후의 회사들에 투자해서 얻을 수 있는 최대이득

 

이처럼 상태공간 및 재정의를 하게 되면, 앞선 부분 문제의 일관성이 유지된다.

현재 company_idx의 값을 뽑았다면, invest(company_idx + 1, capacity - 현재 cost)로 앞선 정의가 유지됨을 볼 수있다.

일반적인 완전 탐색에서는 앞선 선택이 뒤에 선택에 영향을 준다.

완전 탐색에  인덱스 방식을 사용하면, 앞선 선택이 뒤의 선택에 영향을 주지 않는다.

이는 문제의 최적 부분 구조를 만들 수 있다는 것이다!

 

코드는 다음과 같이 구성된다.

최적 부분 구조를 가지기 때문에 아래와 같이 재귀 함수로 우아하게 작성할 수 있다.

def invest(company_idx: int, capacity: int) -> int:
    if company_idx == m\
            or company_idx < 0:
        return 0
    
    if (ret := cache[company_idx][capacity]):
        return ret
    
    ret = invest(company_idx+1, capacity)

    for money in range(1, capacity+1):
        ret = max(ret,
                  invest(company_idx+1, capacity-money)
                  + company_invest[money-1][company_idx])
    
    cache[company_idx][capacity] = ret
    return ret

 

결론

상태 공간을 잘 정의해야 DP를 활용하기 좋다.

tabulation이 성능 측에서는 좋을 수 있지만,

memorization이 좀 더 재귀친화적이고 자연스럽다.