46. 최대 이익 투자(Resource Allocation Problem) 알고리즘 (재귀, 메모이제이션)

1. 개요

최대 이익 투자 알고리즘이란?

- m만원으로 n개의 기업에 투자했을 때, 최대 이익을 찾는 알고리즘이다.

예를들어, 

다음과 같은 투자금에 따른 각 기업의 이익 창출 데이터가 있다.

행: 투자금, 열: 회사

투자액    기업 1    기업 2    기업 3

1            2           3           1

2            4           5           3

3            6           6           7

4            9           8           9

이 때, 투자금 m만원과 n개의 기업이 입력되었을 때, 최대 이익을 구하는 알고리즘이다.

위 데이터와 같이 4만원을 입력하고 3개의 기업을 입력하면, 최대 이익은 10만원이다.

방법은 

기업 2에 1만원을 투자 = 이익 3만원.

기업 3에 3만원을 투자 = 이익 7만원.

둘의 합으로 인해 총 이익 10만원이다.

점화식은

F(m,n) = MAX( (시그마i->m F(i,n-1) + F(m-i,n) ) 이다.

무슨 뜻이냐면, m만원으로 n개 기업에 투자했을 때 최대 이윤은

0만원부터 m만원까지 나머지 기업에 투자했을 때 이윤 + 나머지 돈을 현재 기업에 투자했을 때 이윤

중에서 최대값이 바로 최대 이윤이다.

저기서 0만원부터 m만원까지가 반복적으로 변하는 index이며 이를 유지하기 위해서 적절한 밸런스 조절이 필요하다.

이 문제는 'Resource allocation problem(자원 할당 문제)'로 알려져 있으며,

14회 한국정보올림피아드 중등부 문제(쿨럭쿨럭, 중등부라니!)로 출제되었다.

재귀를 알면 메모이제이션도 쉽게 가능하기에 재귀와 메모이제이션 코드로 풀어냈다.

이 문제를 풀면서 아직 다이나믹 프로그래밍에 대한 개념이 완전하지 않았기 때문에

DP로 풀어내는 과정과 연결된 추가 문제는 다음 포스팅으로 넘긴다. 

원래같았으면 억지로 완성했겠지만 DP 방식에 대한 방법론을 제대로 한 번 집고 넘어갈 필요가 생겼다.

또한, 이 문제에서 0원을 투자하면 이익이 발생하지 않기 때문에 적절한 조정을 위해서 

배열의 index를 하나씩 더 높게 잡아 기존처럼 만원은 배열의 index 0이 아니라 index 1이다.

무슨뜻이냐면 배열의 index가 0이면 0원을 뜻하고, 0개 기업, 즉 남아있는 기업이 없다는 것을 뜻한다.

2. 문제

m만원을 입력하고 n개의 기업을 입력했을 때, 위 개요의 데이터에서 최대 이윤값을 뽑아라.

(재귀와 메모이제이션 두 가지 방법으로 작성하시오.)

3. 코드

IVST란 Investment(투자)의 약자다.

profit은 이윤을 뜻한다.

3-1) 재귀

3-2) 메모이제이션

3-3) 출력

4. 정리

정리로는 이번 재귀와 메모이제이션, 그리고 다이나믹 프로그래밍을 새로 공부하면서 기존에 내가 부족했던 것이

무엇인지 알아가는 중이다. 이제야 결국 알고리즘의 도출을 이렇다.

가장 중요한 것은 점화식이다.

규칙을 통해 점화식을 찾아내야 한다.

그리고 찾아낸 점화식을 재귀적인 방법이든 반복적인 방법이든 작성할 수 있어야 한다.

이 후, 위의 재귀와 반복 두 가지 방법을 빠르게 만들어 주는 것이 바로

메모이제이션과 다이나믹 프로그래밍인 것이다.

이 방법론에 대해서 머릿속에 완전히 정립되면 한 번 제대로 포스팅을 남겨야 겠다.