[알고리즘] 프로그래머스 - 땅따먹기

프로그래머스 | 땅따먹기

⭐️ 문제해결 과정

---

처음에는 재귀 혹은 반복문으로 행의 길이 만큼 반복하고, 하나의 열에서 최댓값 및 최댓값의 인덱스값을 할당(기억)하여 그 다음 인덱스부터는 열에서 최댓값의 인덱스값을 0으로 대체한 다음 위 과정을 반복하면 되는줄 알았다. 어찌저찌 IDE에서는 테스트 통과를 했기 때문에. 하지만 하나같이 런타임 에러가 났다.

function solution(land) {
  let answer = 0;
  let maxIndex = 0;

  // 시도2 => 반복문, 런타임 에러

  for (let i = 0; i < land.length; i++) {
    let x = land[i];
    // 단, 한 행씩 내려올 때 열에서 maxIndex를 0으로 대체하고 큰값을 찾아야한다.
    if (i > 0) {
      x = String(x)
        .replace(x[maxIndex], 0)
        .split(',')
        .map((item) => +item);
    }
    // 한 행(row)가 시작될 때마다 그 행의 최댓값을 구하여 answer에 누적시켜준다.
    const maxScore = Math.max(...x);
    answer = answer + maxScore;
    maxIndex = x.indexOf(maxScore);
  }

  // 시도1 => 재귀함수, 런타임 에러
  const self = (land, index, maxIndex) => {
    // 한 행씩 내려올 때, row배열에서 maxIndex에 요소를 0으로 대체하기
    let row = land[index];
    if (index) {
      row = String(row)
        .replace(row[maxIndex], 0)
        .split(',')
        .map((item) => +item);
    }
    // 한 행(row)가 시작될 때마다 그 행의 최댓값을 구한다.
    const maxScore = Math.max(...row);
    answer = answer + maxScore;
    // 기저조건: 마지막 인덱스면 재귀함수 종료
    if (index === land.length - 1) return;
    // 만약 index가 0이면,(즉 1행부터 땅을 밟으며 한 행씩 내려오므로)

    self(land, index + 1, row.indexOf(maxScore));
  };

  self(land, 0, 0);

  return answer;
}

그래서 다른 사람의 문제풀이를 참고해보니, DP라는 알고리즘을 활용하여 푸는 문제였다. 사실 바로 이해가 가지 않아서 해당 알고리즘에 대해서 찾아 본 뒤에야 왜 이렇게 풀어야 하는지 이해가 갔다. 아래 제한사항에서 보면 행의 개수가 100,000이하의 자연수이기 때문에 이럴 경우 경우의 수가 정말 많아질 수도 있는 문제였다.

제한사항
행의 개수 N : 100,000 이하의 자연수
열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
점수 : 100 이하의 자연수

그래서 최종적인 내 코드는 아래와 같다. (문제가 안풀려서 다른분의 코드를 참고했다.)

function solution(land) {
  // 1. 0번 인덱스 이후의 1, 2번 인덱스부터 시작한다.
  for (let i = 1; i < land.length; i++) {
    // 2. 열의 4개의 요소를 반복문으로 탐색한다.
    for (let j = 0; j < 4; j++) {
      // 3. 이전 열에서 현재 인덱스를 제외한 요소들 중 최댓값 구하기
      const preMaxNum = Math.max(...land[i - 1].filter((_, preI) => j !== preI));
      // 4. 현재 열의 요소들에 각각 위의 최댓값을 더해준다.
      land[i][j] = land[i][j] + preMaxNum;
    }
  }

  return Math.max(...land.pop());
}

💭 학습한 부분

---

다이나믹 프로그래밍(Dynamic Programming - DP)

유튜브 | DP 동적계획 다이나믹 프로그래밍 알고리즘 설명 10분만에 이해하기 (정수 삼각형 문제풀이)
블로그 | 프로그래머스 코딩테스트 연습 Level 2 - 땅따먹기 (JavaScript)

☑️ 기억하기 알고리즘, 기억하며 풀기의 목적

1. 메모리를 사용하여 => 배열 혹은 자료구조를 만든다
2. 중복 연산을 줄이고 => 연산한 결과를 배열에 담는다
3. 중복 연산을 줄여서 수행 속도를 개선한다.

즉, 연산한 내용을 기억해놓고 다음에도 그 연산이 필요할 때 기억해놓은 값을 사용하면서 문제를 풀기 위한 목적

☑️ 다이나믹 프로그래밍 문제를 알아보고 구분하기

1. DFS/BFS로 풀 수 있지만 경우의 수가 너무 많은 문제
2. 경우의 수들에 중복적인 연산이 많은 경우