Dynamic Programming _ Memoization 설명 및 적용 #2(숫자형)

2022.10.06 - [Data Structure & Algorithm] - Dynamic Programming _ Memoization 설명 및 적용 #1

위 글에 이어 2번째 시리즈입니다

Cansum 예시 _

첫번째 게시물의 Dynamic Programming 레시피를 바탕으로 cansum(targetSum, numbers) 주어진 numbers로 targetSum 을 만들 수 있는지 cansum함수를 만들어보겠습니다. (cansum 함수는 targetSum을 만들 수 있는지, 없는지 True/False를 반환해야 합니다)

 

 

cansum(7,[5,3,4,7])을 기반으로 발생가능한 경우의 수를 tree로 나타냈습니다.

 

 

이 케이스를 통해 마지막 노드가 0이 되면 True를 반환하고 그 외의 경우에는 False 를 반환함을 알 수 있습니다

각 노드 경우의 수를 모아보면 False,True,True,True

즉 최종 output은 numbers를 통해 targetSum 반환이 가능하다 => True입니다

 

 

const canSum = (targetSum,numbers) => {
    if (targetSum ==0) return true;
    if (targetSum < 0) return false;
    
    for (let num of numbers) {
    	const remainder = targetSum - num;
        if (canSum(remainder,numbers) === true){
            return true;
        }
    }
    return false;
};

 

이 코드의 Time complexity를 보겠습니다. 

m = targetsum, n = array length 

 

이 트리의 최대 높이는 targetsum에서 1씩 빼는 경우 트리의 길이가 최대가 되므로 m입니다

각 노드에는 중복가능한 number를 배정할 수 있기 때문에 각 n씩 노드를 생성할 수 있습니다.

 

 

따라서, 여기서 시간 효율성은 m 단계마다 n개씩 계산 해야 하므로 O(n^m)임을 알 수 있습니다.

Space complexity는 tree의 높이인 O(m) 입니다

 

 

코드에 어떤 비효율이 발생하고 있는지 보기 위해 그래프를 다시 보겠습니다.

이 역시 중복된 계산이 똑같은 연산을 할 때마다 수행되고 있습니다.

 

 

기존 코드에 효율성을 높이기 위해 memoization 을 해보겠습니다.

 

const canSum = (targetSum,numbers,memo={}) => {
    if (targetSum in memo) return memo[targetSum];
    if (targetSum ==0) return true;
    if (targetSum < 0) return false;
    
    for (let num of numbers) {
    	const remainder = targetSum - num;
        if (canSum(remainder,numbers, memo) === true){
            memo[targetSum] = True;
            return true;
        }
    }
    memo[targetSum] = false;
    return false;
};

 

이 코드의 time complexity는 O(m*n), Space complexity 는 O(m)입니다

중복된 계산을 할 필요는 없어졌지만 m의 높이동안 n 번의 가지를 만들어야 하기 때문에 O(m*n)이 됩니다

 

Howsum 예시 _

 

True/False를 반환하는 TargetSum과 달리, TargetSum을 만드는 조합을 반환하는 HowSum을 공부해보겠습니다.

(만약, 조합이 모든 경우의 수에 부합하지 않으면 null을 반환해야 합니다)

 

const howSum = (targetSum,numbers) => {
    if (targetSum === 0 ) return [];
    if (targetSum <0) return null;
    
    for (let num  of numbers){
    	const remainder = targetSum -num;
        const remainderResult = howSum(remainder,numbers);
        if (remainderResult != null){
        	return [...remainderResult, num];
        	}
    }
    return null;     
 };

 

이 Brute Force approach 는 return [...remainderResult,num]으로 인해 O(n^m*m)의 time complexity를 가지고 

O(m) 의 space complexity를 가집니다

 

 

Memoization 적용)

const howSum = (targetSum,numbers,memo={}) => {
    if (targetsum in memo) return memo[targetSum];
    if (targetSum === 0 ) return [];
    if (targetSum <0) return null;
    
    for (let num  of numbers){
    	const remainder = targetSum -num;
        const remainderResult = howSum(remainder,numbers,memo);
        if (remainderResult != null){
        	memo[targetSum] = [...remainderResult, num];
        	return memo[targetSum]
            }
    }
    memo[targetSum] = null;
    return null;     
 };

 

Time complexity: O(n*m*m) = O(n*m^2)

기존 n^m의 시간복잡도가 중복을 제거함에 따라 n*m이 되지만 return  function에서

m번의 계산이 더 필요하므로 n*m*m이 됩니다

 

Space complexity = O(m**m) = O(m^2)

memo의 key는 고유한 값들을 가지겠지만, memo value array는 m만큼의 길이를 가지기 때문에 O(m*m)이 됩니다.

 

Bestsum 예시 _

TargetSum을 만드는 모든 조합을 찾는 HowSum과 달리, 가장 짧은 숫자 조합을 찾는 문제입니다

 

const bestSum = (targetSum,numbers)=> {
    if (targetSum == 0) return [];
    if (targetSum < 0) return null;
    
    let shortestCombination = null;
    
    for (let num of numbers) {
    	const remainder = targetSum - num;
        const remainderCombination = bestSum(remainder,numbers);
        if (remainderCombination != null) {
        	const combination = [...remainderCombination, num];
            if (shortestCombination === null || combination.length < shortestCombination.length)
            	shortestCombination = combination;
        }
    }

   return shortestCombination
};

 

이 코드는 이전 HowSum의 Brute force 와 동일하게 O(n^m*m)의 time complexity를 가지지만,

space complexity의 경우 shortestCombination 이라는 변수가 매 계산때마다 최대 m번 반복되므로

O(m*m)의 space complexity를 가지게 됩니다

 

 

const bestSum = (targetSum,numbers,memo={})=> {
    if (targetSum in memo) return memo[targetSum];
    if (targetSum == 0) return [];
    if (targetSum < 0) return null;
    
    let shortestCombination = null;
    
    for (let num of numbers) {
    	const remainder = targetSum - num;
        const remainderCombination = bestSum(remainder,numbers,memo);
        if (remainderCombination != null) {
        	const combination = [...remainderCombination, num];
            if (shortestCombination === null || combination.length < shortestCombination.length)
            	shortestCombination = combination;
           }
        }
    }
   memo[targetSum] = shortestCombination;
   return shortestCombination;
};

 

Time complexity: O(n*m*m) = O(n*m^2)

Space complexity = O(m*m)

 

** 이 글은 freecodecamp의 Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges 강좌를 기반으로 정리된 글입니다. 강의 자체가 구성이 너무 좋고 예시도 풍부해서 보시길 추천드려요 :))

https://www.youtube.com/watch?v=oBt53YbR9Kk&t=179s&ab_channel=freeCodeCamp.org