[데일리코딩] tiling

문제

• 타일의 크기는 2*1
• 높이는 2로 고정, 너비는 n
• 타일을 붙일 수 있는 모든 경우의 수 리턴

개념정리

🔍 Dynamaic Programming(DP)란?

• 입력 크기에 대해 중복되는 부문 문제(subproblem)이 발생하는 경우(or 문제가 최적 부분구조로 이루어져있을때), 이를 한 번만 계산하고 이전에 계산한 값을 재활용하여 전체문제를 효율적으로 해결하는 기법이다.
• DP의 핵심 개념은 Memoization이다. 메모이제이션은 이전에 계산한 값을 저장해두어 중복 계산은 피하여 계산량을 줄이는 방법이다.
• DP는 주로 최적화 문제를 해결하는데 사용된다.
  • 피보나치 수열 계산
  • 최장 공통 부분 수열(LCS, Longest Common Subsequence)
  • 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

🔍 DP with Tabulation

• 리스트에 값을 기록하는 방법이다.
• 반복문을 사용하여 밑에서부터 값을 계산하기 때문에 상향식 접근 방식이다. (bottom-up)
• 스택 과부화가 걸릴 위험은 없지만 필요없는 값의 계산이 필요할 수도 있다.

🔍 작성 코드

• for 반복문이 n번 반복되기 때문에 시간복잡도는 O(N)이다.
• 수정사항
  처음에는 result 변수 선언시 let 키워드를 사용했는데, 이는 함수의 외부에서도 수정이 가능하는 등의 문제가 있을 것이라 생각되어 const로 변경하였다.

let tiling = function (n) {
  const result = [0, 1, 2]; 
  for (let i = 3; i <= n; i++) {
    result[i] = result[i-1] + result[i-2]; 
  }
  return result[n]; 
};

🔍 DP with Memoization

• cashe에 값을 기록하는 방법이다.
• 재귀를 이용하여 위에서부터 값을 계산하기 때문에 하향식 접근방식이다.
• 값을 위에서부터 계산하기 때문에 필요없는 계산은 하지 않아도 된다.
• 하지만 스택이 너무 많이 쌓여서 과부하가 걸릴 수도 있다.

🔍 작성 코드

let tiling = function (n) {
  const memo = [0, 1, 2];
  const aux = (size) => {
    if (memo[size] !== undefined) return memo[size];
    if (size <= 2) return memo[n];
    memo[size] = aux(size - 1) + aux(size - 2);
    return memo[size];
  };
  return aux(n);
};

🔍 두 코드 비교하기

• 시간복잡도는 O(N)으로 같다.
• 하지만 2번 코드는 재귀적으로 동작하기 때문에 함수 호출과 스택 메모리에 오버헤드가 발생한다.
• 따라서 n의 사이즈가 크다면 첫번째 코드가 더 효율적이다.

🔍 공간최적화 리팩토링하기

공간최적화란 알고리즘에서 사용하는 메모리 공간을 최대한 줄여서 실행시간과 메모리 사용량 모두 최적화하는 기법이다.

• 계산한 값을 모두 저장하는 배열 result를 사용하지 않고, 필요한 값만 변수에 저장하여 사용했다.
• 메모리 사용량은 O(1)이다.

let tiling = function(n) { 
	let prev = 2; 
	let prePrev = 1;
	let current = 0; 
	for (let i = 3; i <= n; i++) {
		current = prev + prePrev;
		prePrev = prev;
		prev = current;
	}
return n === 1 ? 1 : n === 2 ? 2 : current;
}