28주차 알고리즘

멀리 뛰기

// 피보나치를 활용하여 2칸 남았을 때와 1칸남을때의 경우의 합을 구하면 전체 경우의 수이다.
function solution(n = 3) {
  if (n === 1) {
    return 1;
  } else if (n === 2) {
    return 2;
  }
  let dp = new Array(n);
  dp[1] = 1;
  dp[2] = 2;

  for (let i = 3; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
  }
 
  return dp[n]
}

최소공배수

// 최소공배수는  두곱으로 나눈 최소공약수이다. 
const gcd = (a, b) => {
  if (b === 0) {
    return a;
  } else if (a % b === 0) {
    return b;
  }
  return gcd(b, a % b);
};

const solution = (arr) => {
  let answer = 1;
  for (let index = 0; index < arr.length; index++) {
    answer = (arr[index] * answer) / gcd(arr[index], answer);
  }
  return answer;
};

영어 끝말잇기

// Math.celi는 올림하는 메서드이다. 
function solution(
  n = 3,
  words = [
    'tank',
    'kick',
    'know',
    'wheel',
    'land',
    'dream',
    'mother',
    'robot',
    'tank',
  ]
) {
  let answer = [0, 0];

  for (let i = 0; i < words.length - 1; i++) {
    for (let j = i + 1; j < words.length; j++) {
      if (words[i] === words[j]) {
        words[j] = 0;
      }
    }
  }

  for (let index = 0; index < words.length; index++) {
    if (
      index > 0 &&
      words[index - 1][words[index-1].length - 1] !== words[index][0]
    ) {
      answer[0] = (index % n) + 1;
      answer[1] = Math.ceil((index + 1) / n);
      break;
    }
    if (words[index] === 0) {
      answer[0] = (index % n) + 1;
      answer[1] = Math.ceil((index + 1) / n);

      break;
    }
  }

  return answer;
}

연속 부분 수열 합의 개수

function solution(elements = [7, 9, 1, 1, 4]) {
  let l = elements.length;
  let set = new Set();
  for (let index = 0; index < elements.length; index++) {
    let v = elements[index];
    set.add(v); // 한개 선택
    for (let j = index + 1; j < index + l; j++) {
      //index가 포함된 모든 값
      v += elements[j % l];
      console.log(v);
      set.add(v);
    }
  }

  return set.size;
}