House Robber

2018.08.04

Algorithm

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]

Output: 12

Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

나의 풀이

문제에 주어진 배열이 [1, 2, 3]이라고 했을 때 1 + 3과 2를 비교하게 되고, [1, 2, 3, 4]일 경우는 1 + 3과 2 + 4를 비교하게 되는데 그러면 홀수번과 다음 수를 비교할 때는even = Math.max(1 + 3, 2)이 되고, 짝수번의 요소와 다음 수를 비교하면odd = Math.max(4, 2 + 4)가 된다. 이런 규칙을 이용해서 푸는데, 만약 빈배열이거나 요소가 1개일 경우를 위해even과odd`는 0을 기본값으로 할당해줬다.

// 60ms
var rob = function(nums) {
    let even = 0;
    let odd = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) {
            even = Math.max(even + nums[i], odd);           
        } else {
            odd = Math.max(even, odd + nums[i]);
        }
    }
  return Math.max(even, odd)
}

예전에 푼 프로그래머스 땅따먹기 문제랑 비슷한 것 같다. 이것도 너무 오래 걸렸다. 이런 유형의 알고리즘을 Dynamic Programming(DP)이라고 하는 것 같다.

다른 사람 풀이

빈배열, 배열 요소가 하나일 때, 2개 일때는 따로 값을 반환하고, 3개 이상일 경우부터 n: Max(n+s(n-2), s(n-1))같은 규칙을 따른다.

var rob = function(nums) {
    // 1: 1
    // 1,2: Max(1, 2)
    // 1,2,3: Max(3+s([1]), s([1,2]))
    // 1,2,3,4: Max(4+s([1,2]), s([1,2,3]))
    // n: Max(n+s(n-2), s(n-1))
    if(!nums.length) {
        return 0;
    }
    
    if(nums.length === 1) {
        return nums[0];
    }
    
    if(nums.length === 2) {
        return Math.max(nums[0], nums[1]);
    }
    
    const dp = [];
    
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    // dp[2] = Math.max(nums[2] + dp[0], dp[1]);
    
    for(let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(nums[i]+dp[i-2], dp[i-1]);
    }
    
    return dp[dp.length - 1];
};

Dynamic Programming(DP)

동적 프로그래밍

문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 방법으로 하위 문제의 값을 저장해두어(memozation) 그 하위 문제를 반복해서 풀어야 하는 경우 다시 계산하지 않고 재사용하는 식으로 계산 횟수를 줄일 수 있다.

모든 방법을 일일이 검토해 그 중 최적의 풀이법을 찾아내야 하기 때문에 최적의 방법(혹은 최단 경로)를 찾아내기 위한 시간이 걸리지만 그 결과는 가장 최적의 방법(최단 경로)라고 장담할 수 있다.

이를 이용한 알고리즘으로 최장 공통 부분 수열, 벨만-포드 알고리즘, 배낭문제 등이 있다.

피보나치 수열 문제의 경우 재귀적으로 다음과 같이 풀 수 있다.

1	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

const fibo = (n) => {
  if (n <= 1) return n;
  return fibo(n - 1) + fibo(n - 2);
}

이 경우 fibo(5)를 구할 경우 다음과 같이 계산되는데, fibo(n)이 중복되어 계산되는 부분이 있어서, 전체적인 계산 속도를 떨어뜨린다.(이 알고리즘의 시간 복잡도는 지수함수가 된다.)

fibo(5)
fibo(4) + fibo(3)
(fibo(3) + fibo(2)) + (fibo(2) + fibo(1))
((fibo(2) + fibo(1)) + (fibo(1) + fibo(0))) + ((fibo(1) + fibo(0)) + fibo(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

이를 계산했던 값을 저장하는 메모이제이션을 이용해 동적 프로그래밍 방법으로 풀어본다면 다음과 같이 풀 수 있다. 이렇게 하면 중복되는 계산이 줄어든다.(시간 복잡도는 $O (n)$ 이 된다.)

const fibonacci = (n) => {
    const memo = {0: 0, 1: 1};
    const fibo = (n) => {
        if (n <= 1 || memo[n]) {
            return memo[n]
        } else {
            memo[n] = fibo(n - 1) + fibo(n - 2);
            return memo[n];
        }
    };
    return fibo(n);
}

참고