[프로그래머스][JS]땅따먹기, 피보나치 수

Kyle·2021년 1월 11일

Problem Solving 땅따먹기 프로그래머스 피보나치 수

problem solving

목록 보기

30/36

땅따먹기

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

N행 4열로 이루어진 2차원 배열에서 연속해서 같은 열을 밟을 수 없는 조건으로 가장 높은 수의 합을 구하는 문제.

첫번째 시도 dfs

첫번째로 dfs로 시도를 했다. 제한사항에 N은 10만 이하의 개수를 보고 안될 것 같다는 생각을 하긴했지만 그래도 시도해봤다.

function solution(land) {
  let answer = new Set();

  const dfs = (arr, sum = 0) => {
    if (!arr.length) {
      return answer.add(sum);
    } else {
      for (let i = 0; i < arr[0].length; i++) {
        sum += arr[0][i];
        const restArr = arr.slice(1).map((v) => [...v]);
        if (restArr.length) restArr[0][i] = 0;
        if (arr[0][i] === 0) continue;
        else dfs(restArr, sum);
        sum -= arr[0][i];
      }
    }
  };
  dfs(land);

  return Math.max(...answer);
}

역시나 시간 초과가 발생했다.

이때 어떻게 풀어야 되나 알아보다가 질문하기에서 다이나믹프로그래밍을 이용해야 된다는 글을 발견하고 다이나믹 프로그래밍에 대해 간단하게 공부했다.

다이나믹 프로그래밍(dp)으로 어떻게 풀었을까

해결방법

사실 이 풀이가 dp인지는 모르겠다.
1. answer에 2차원 배열의 첫번째 배열을 넣는다. 앞으로 answer의 4개의 값은 각 인덱스에서 최고로 높은 경우의 수만 저장한다.
2. 이제 answer로 빠진 첫번째를 제외한 land를 한행 한행 for문을 통해서 answer를 업데이트해준다.
3. tmpAnswer에 각 인덱스에 맞는 answer의 최대값 + land[i][j]을 넣어주고 answer를 tmpAnswer로 업데이트해준다. 예시를 보면 이해가 될 것같다.
ex)answer = [1,2,3,4] , land[i] = [6,7,8,9] 일때
tmpAnswer[0] = 6 + [2,3,4]중 최대 4 = 10
tmpAnswer[1] = 7 + [1,3,4]중 최대 4 = 11
tmpAnswer[2] = 8 + [1,2,4]중 최대 4 = 12
tmpAnswer[3] = 9 + [1,2,3]중 최대 3 = 12
==> tmpAnswer = [10,11,12,12]
answer = tmpAnswer 로 answer업데이트 해주기
4. answer중 최대값을 출력한다.

code

function solution(land) {
  let answer = land.shift();
  for (let i = 0; i < land.length; i++) {
    tmpAnswer = [];
    for (let j = 0; j < 4; j++) {
      const tmp = answer.filter((v, idx) => idx !== j);
      tmpAnswer.push(Math.max(...tmp) + land[i][j]);
    }
    answer = tmpAnswer;
  }
  return Math.max(...answer);
}

피보나치 수

문제: https://programmers.co.kr/learn/courses/30/lessons/12945

피보나치를 구하는 문제입니다. 뭔가 이 문제는 이상했습니다.
제가 아래 설명할 2가지 방법은 이 문제의 정답은 아닙니다.
통과한 정답은 맨아래에 작성해두겠습니다.

해결방법 1 - 메모이제이션

메모이제이션 사실 말이 어렵지만 간단하게 말하면 객체같은 곳에 값을 저장해두고 그곳에 필요한 값이있으면 찾아서 사용하는 것입니다. 이를 통해 불필요한 계산을 줄일 수 있습니다.

아래의 코드에서는 객체에 값을 저장하겠습니다. 코드에 주석으로 설명하겠습니다.

function solution(n) {
  const cache = {}; //값을 저장할 객체
  const fib = (num) => {
    if (num < 2) return num; //0=>0, 1=>1
    else if (cache[num]) return cache[num]; // 만약 cache객체에 값이 있으면 사용한다.
    else { //없다면
      cache[num] = fib(num - 1) + fib(num - 2); //원래 재귀형식으로 구해서 cache객체에 저장
      return cache[num]; //그 값을 반환한다.
    }
  };
  return fib(n);
}

해결방법 2 - 다이나믹 프로그래밍

내가 다이나믹 프로그래밍 개념이 잘 잡혀있지 않아 이게 다이나믹 해결방법인지는 잘 모르겠습니다. 반복문을 이용해 a,b,c 3개의 수를 이용해서 계속 업데이트 해주는 방식입니다.

function solution(n){
    let a=1 // fib(0)일때
    let b=1 // fib(1)일때
    for(let i=3; i<=n; i++){
        let c = a+b //이전 2개를 더하는 것
        a=b  //a업데이트
        b=c  //b업데이트
    }
    return b  //b에 뒤의 두수가 더해진게 저장돼 있으므로 반환
}

정답코드

function solution(n){
    let a=1
    let b=1
    for(let i=3; i<=n; i++){
        let c = a%1234567+b%1234567   
        a=b%1234567   
        b=c%1234567   
    }
    return b%1234567   
}