Level 2️⃣ - 땅따먹기와 동적 프로그래밍

동적 계획법이란 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법입니다. 엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기 보다는 문제를 해결하는 패러다임에 가깝습니다. 어떤 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구했던 해를 활용하는 방식의 알고리즘 입니다.

 

 

복잡한 문제를 간단한 여러개의 문제로 나누어 푼다는 것이 DP의 개념인데 피보나치 수열이 대표적인 예시로 등장을 한다.

 

피보나치 수열

흔히 재귀함수를 사용해 피보나치 수열을 구현할 수 있다.

function fibo(n) {
  if (n === 1) return 1;
  if (n === 2) return 1;
  return fibo(n - 1) + fibo(n - 2);
}

function solution() {
  return fibo(5);
}

console.log(solution());

 

하지만 문제점이 있다. 중복 계산으로 인해 시간 복잡도의 효율성이 떨어진다는 것이다.

재귀함수의 호출 과정을 트리로 표현해보면 중복되는 계산이 여러번 반복되는 것을 알 수 있다.

만일 N의 크기가 커진다면 그 횟수는 더욱 늘어날 것이다. 

이 문제를 해결하기 위해서는 연산된 값을 기억할 수 있는 메모이제이션이 필요하다.

 

동적 계획법의 알고리즘은 다음과 같다.

1. 문제를 부분 문제로 나눈다.
2. 가장 작은 문제의 해를 구한 뒤, 테이블에 저장한다.
3. 테이블에 저장된 데이터로 전체 문제의 해를 구한다.

따라서 DP를 이용해 피보나치를 구현하면 다음과 같다. 아래의 링크도 DP를 이용해 구한 방법이다.

https://ukgi-dev.tistory.com/107

Level2️⃣ - 피보나치 수

const arr = [];

function fibo(n) {
  if (n === 1) return 1;
  if (n === 2) return 1;
  if (arr[n]) return arr[n];
  return (arr[n] = fibo(n - 1) + fibo(n - 2));
}

console.log(fibo(5));

---

땅따먹기

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

 

🚀문제해석

처음에 접근 방법은 각 열마다 가장 큰 값을 찾아 그 값을 건너고 건넌 열의 인덱스를 저장하고 있다가 다음 행으로 넘어갈 때 저장한 인덱스를 제외한 요소들 중 가장 큰 값을 찾아 건너는 방법으로 생각했다. 일종의 그리디 기법인데 잘못 생각하고 있었다.

 

| 1 | 2 | 3 | 4 |

| 1 | 2 | 3 | 7 |

| 3 | 5 | 2 | 1 |

 

만일 이렇게 되어있고 내 논리대로라면 첫번째 행에서는 4를 선택해야된다. 이렇게 되면 두번째 행에서 가장 큰 값인 7을 선택할 수 없게된다. 그렇다면 3을 선택하고 그 다음 행에서는 5를 선택하게 되므로 최댓값은 12이다. 하지만 답은 12가 아니라 첫번째 행에서 3을 선택하고 두번째 행에서 7을 선택하고 세번째 행에서 5를 선택해 총 15가 나와야한다.

 

이런 경우 복잡한 문제를 간단한 문제로 나누어 해결해보는 시도를 해야한다.

사실 문제를 많이 접해보지 않아서 왜 DP로 접근을 해야하는지에 대한 감이 많이 부족하다. 추후에 감이 왔을 때, 이 문제를 왜 DP로 접근해야하는지 이유를 스스로 적어보자. 왜라는 질문에 항상 접근해야한다.

 

한 행씩 내려오면서 거기까지 내려올때의 최고의 합을 기억한다면 어떨까?

| 1 | 2 | 3 | 4 |

| 1 | 2 | 3 | 7 |

| 3 | 5 | 2 | 1 |

 

두번째 행부터 자기 바로 위에있는 값을 제외한 요소들 중에 최댓값을 더했을 때가 최고의 합이다.

두번째 행에 이 원리를 적용해보면 다음과 같다.

| 1 | 2 | 3 | 4 |

| 5 | 6 | 7 | 10 |

| 3 | 5 | 2 | 1 |

 

세번째 행도 마찬가지로 같은 과정을 반복하면 된다. 

| 1 | 2 | 3 | 4 |

| 5 | 6 | 7 | 10 |

| 13 | 15 | 12 | 8 |

 

따라서 최적의 합을 구했을 때 나오는 가장 최댓값인 15가 정답이 된다. 직접 구해보아도 1행에서 3, 2행에서 7, 3행에서 5를 선택하는 것이 구할 수 있는 가장 큰 값이다.

---

코드

느낀점은 작은 부분의 문제를 해결할 수 있는 논리로 전체 문제를 해결할 수 있다면 DP의 방법을 고려해보자는 것이다.

function solution(land) {
    for(let i = 1; i<land.length; i++){
        land[i][0] += Math.max(land[i-1][1], land[i-1][2], land[i-1][3]);
        land[i][1] += Math.max(land[i-1][0], land[i-1][2], land[i-1][3]);
        land[i][2] += Math.max(land[i-1][0], land[i-1][1], land[i-1][3]);
        land[i][3] += Math.max(land[i-1][0], land[i-1][1], land[i-1][2]);
    }
    return Math.max(...land[land.length - 1]);
}