로드-커팅 문제(Cutting Stock Problem)

로드-커팅 문제(Cutting Stock Problem) : 주어진 장작을 다양한 크기로 잘라 최대한의 이익이 나도록 하는 문제.

도매로 장작을 구입해서 소매로 판매하는 회사에 근무한다고 가정해보자. 이 회사는 장작을 다양한 크기로 잘라서 최대한의 이익을 얻는다. 각각 서로 다른 길이를 갖고 있는 장작의 가격은 수시로 변경되며 따라서 주어진 크기의 장작에 대해 최대한의 이익을 구하는 프로그램을을 작성해야 한다. 

단순한 재귀 호출을 사용한 해결
5인치의 장작이 있다면 그 길이에 대한 가격을 찾을 수 있다. 이 예제에서 5인치 장작의 가격은 2달러 이다, 하지만 4인치도 2달러 이기 때문에 이 경우에는 5인치를 5인치와 1인치로 자르는 방법이 더 좋다. 이 방법을 사용하면 n의 길이에 대한 수익을 구할 수 있으며, 그 방법은 해당 길이를 가능한 2n-1로 자르는 것이 가장 큰 수익을 얻을 수 있다.

주어진 길이 n에 대해서 max(no cut, cut(1, n-1), cut(2, n-2), ....)와 같이 계산할 수 있다.

이를 코드로 작성하면 아래와 같이 작성 할 수 있다. 
이 메서드는 특정 길이의 수익을 찾는데 주어진 길이에 추가 하여 다른 길이의 수익을 재귀적으로 찾게 된다. 최종적으로는 그 중에 최대 수익을 구하도록 되어 있다.

final List<Integer> priceValues = Arrays.asList(1, 2, 4, 2, 2, 2, 1, 8, 9, 15);
public int maxProfit(final int length) {
    int profit = (length <= prices.size()) ? prices.get(length - 1) : 0;
    for (int i = 1; i < length ; i++) {
        final int currentProfit = maxProfit(i) + maxProfit(length - i);
        if (currentProfit > profit) profit = currentProfit;
    }
    return profit;
}

이를 수행해 보면 length 값이 증가할 수록 복잡도가 O(2^(n-1) ) 와 같이 지수 형태로 증가 하기 때문이고, 다양한 길이에 대한 반복된 연산을 계속 수행한다.

이를 개선하기 위해 재귀 연산을 재활용하는 메모이제이션 기법을 사용한다.
메모이제이션을 사용하면 처음으로 연산하는 경우에만 연산을 실행하고, 이전에 한 번이라도 연산을 한 적이 있다면 과거의 연산 결과를 사용한다. 

자바 8 람다의 힘 책에서는 이를 람다로 풀었었었는데, 이를 람다가 아닌 일반 해쉬 맵을 사용한다면..

private final Map<Integer, Integer> store = new HashMap<>();

public int maxProfit(final int length) {
    int profit = (length <= prices.size()) ? prices.get(length - 1) : 0;
    if (store.get(length) != null) {
        return store.get(length);
    } else {
        for (int i = 1; i < length ; i++) {
            final int currentProfit = maxProfit(i) + maxProfit(length - i);
            if (currentProfit > profit) profit = currentProfit;
        }
        store.put(length, profit);
        return profit;

    }
}

위 같은 방법으로 이미 호출됬던 재귀 호출에 대한 값을 hashmap에 저장해 둠으로써 연산 속도를 엄청나게 올릴 수 있다.

기존 방법으로 할 경우 22를 값으로 줄 경우 무려 40초가 걸리는데, 맵을 사용하는 방법으로 변경하면 1초도 안걸린다. 

이걸 Java 8 람다 스타일로 좀 바꿔 보면 아래 처럼 작성할 수 있다. 
.computeIfAbsent는 map에 추가된 메서드로 키에 해당하는 값이 있으면 그 값을 리턴해주고 없으면 새로운 값을 할당한 다음 그것을 리턴해준다.

public int maxProfit(final int length) {
   return store.computeIfAbsent(length, (key) -> {
            int profit = (length <= prices.size()) ? prices.get(length - 1) : 0;
            for (int i = 1; i < length; i++) {
                final int currentProfit = maxProfit(i) + maxProfit(length - i);
                if (currentProfit > profit) profit = currentProfit;
            }
            store.put(length, profit);
            return profit;
        }
    );
}

여기서 느낄 수 있었던 것은 재귀 함수를 작성해서 문제를 해결한다. 라는 생각까지만 하지말고 이를 좀 더 머리를 써보면(여기서는 맵을 사용한 메모이제이션) 좀 더 성능이 좋은 코드를 작성할 수 있다는 것이다. 

따로 알고리즘 공부를 하진 않지만 기존 알고리즘에 이런 메모이제이션 기법을 도입하는 것은 참신한 기법인듯.
프로그래밍 경험치가 +1 되는 기분이 들었다.