스터디 기록 21

문제 목록

❤️‍🔥 멀리 뛰기

function solution(n) {
  // 경우의 수??
  // n까지의 피보나치 수열을 구하고 1234567 나눈 나머지 리턴

  let fibo = [0, 1];
  for (let i = 2; i <= n; i++) {
    fibo.push((fibo[i - 1] + fibo[i - 2]) % 1234567);
  }
}

solution(4);

/*
1 => 1 
! 1 방법 = 1
2 => 1, 1 / 2 = 2
! 2 방법 = 2
3 => 1, 1, 1 / 2, 1 / 1, 2 = 3
! 3 방법 = 3
4 => 1, 1, 1, 1 / 2, 2 / 2, 1, 1 / 1, 2, 1 / 1, 1, 2 = 5
! 4 방법 = 5
5 => 1, 1, 1, 1, 1 / 2, 2, 1 / 2, 1, 2 / 1, 2, 2 / 2, 1, 1, 1 / 1, 2, 1, 1 / 1, 1, 2, 1 / 1, 1, 1, 2
! 5 방법 = 8
6 => 1, 1, 1, 1, 1, 1 / 2, 2, 2 / 1, 1, 2, 2 / 2, 2, 1, 1 / 1, 2, 1, 2 / 1, 2, 2, 1 / 2, 1, 1, 2 / 2, 1, 2, 1 / 1, 1, 1, 1, 2 / 1, 1, 1, 2, 1 / 1, 1, 2, 1, 1 / 1, 2, 1, 1, 1 / 2, 1, 1, 1, 1
! 6 방법 = 13

도달 방법의 수 = [1, 2, 3, 5, 8, 13 ...]

1 + 2 = 3
2 + 3 = 5
3 + 5 = 8

피보나치 수열??

*/

입력받은 매개변수 n의 모든 경우의 수를 구하는 문제였다. 1부터 n까지 하나하나 어떻게 나오는지 확인해 보고 몇 가지의 방법이 나왔는지 보다보니 피보나치로 풀 수 있다는 것을 알게 되었다! 생각보다 간단했던 문제였다

const factorial = (n) => {
    if(n === 0) return BigInt(1);
    let num = BigInt(1);
    let a = BigInt(n);
    while(a != BigInt(1)){
	@@ -10,6 +10,7 @@ const factorial = (n) => {
}

function solution(n) {
    // https://bhsmath.tistory.com/153
    // n개를 나열하는 방법 n!/ 같은거 3개를 나열하는 법 3!, 같은거 2개를 나열하는 법 2!
    // 2 2, 1, 1, 1 
    // 5!/(3! * 2!) = 10
    // 묶음을 구하는 공식?
    // 두개씩 뽑는 경우 n / 2 
    // n이 4일 경우 2, 1, 0 묶음 수가 다음과 같이 선택됨.
    // 2, 2 2
    // 1, 1 1 2, 1 2 1, 2 1 1
    // 0, 1 1 1 1
    // n 3
    // 1, 2 1, 2 1
    // 0  1 1 1
    let answer = BigInt(0);
    const maxTwoNum = Math.floor(n / 2);
    for(let twoNum = 0 ; twoNum <= maxTwoNum ; twoNum++){
        const oneNum = n - (twoNum * 2)
        const length = twoNum + oneNum;
        const value = factorial(length) / (factorial(oneNum) * factorial(twoNum));
        answer += value;
    }
    return Number(answer % BigInt(1234567));
}

효근님 코드 효근님은 피보나치를 사용하지 않고 같은 것이 있는 순열을 사용하여 풀이하셨다. 색달라서 좋았다... 효근님이 주석에 담아주신 https://bhsmath.tistory.com/153 이곳 블로그를 참고하여 이해를 하였다.

❤️‍🔥 H-Index

function solution(citations) {
  /*
  H-지수 => 특정 연구원의 연구 성과를 평가하기 위한 지표, 발표 논문수와 피인용수를 사용해 학문적 역량 측정
 H-지수 구하기 => 전체 논문 중 많이 인용된 순으로 정렬 후, 피인용수가 논문수와 같아지거나 피인용수가 논문수보다 작아지기 시작하는 숫자!

 참고: https://www.ibric.org/myboard/read.php?Board=news&id=270333
  */

  /* 내림차순 정렬 후, 인용 횟수 h가 h편이 될 때 바로 리턴 */

  citations.sort((a, b) => b - a);

  for (let h = 0; h < citations.length; h++) {
    //피인용수가 논문수보다 작아지기 시작할 때 리턴
    if (citations[h] <= h) {
      return h;
    }
  }

  return citations.length;
}
solution([3, 0, 6, 1, 5]);
/*
 ? 많이 인용된 순으로 정렬 후, 
 ? 인용수가 논문수와 같아지거나 피인용수가 논문수보다 작아지기 시작하는 숫자

피인용수          논문수      boolean
6                 1          false
5                 2          false
3                 3          true   (당첨!!)
1                 4
0                 5


*/

문제 자체를 이해하기 어려워서 검색해서 논문을 참고해서 이해한 문제... 처음에 이해를 못 하겠었는데 정말 문제에 나온 문장 그대로였다. 피인용수가 논문수보다 작아지기 시작하는 시점에 바로 리턴을 하게 해주었다!

❤️‍🔥 [1차 캐시]

function solution(cacheSize, cities) {
  /* 
  LRU(제일 오래 사용하지 않은 페이지 교체)
  Set 객체 사용해서 풀어보자!!
  1. has해서 넣을 데이터가 있는지부터 먼저 확인
  2. 있는 경우 지금 넣을 데이터 삭제, cHit니까 +1
     없는 경우 캐시 꽉 참 => 캐시 첫번째 값을 저장 후, 첫번째 값 삭제, cMiss니까 +5
              캐시 안 참 => cMiss니까 +5
  3. 지금 넣을 데이터 add 해 주기

 */

  let runtime = 0;
  const cache = new Set();
  const cHit = 1;
  const cMiss = 5;

  if (cacheSize === 0) return cities.length * cMiss;
  cities = cities.map((ele) => ele.toUpperCase());

  for (let i = 0; i < cities.length; i++) {
    const boolean = cache.has(cities[i]);
    console.log(cities[i]);
    console.log(cache.has(cities[i]));

    if (boolean) {
      cache.delete(cities[i]);
      runtime += cHit;
    } else if (cache.size === cacheSize) {
      const first = [...cache][0];
      cache.delete(first);
      runtime += cMiss;
    } else {
      runtime += cMiss;
    }
    cache.add(cities[i]);
  }
  return runtime;
  console.log(runtime);
}

solution(3, [
  'Jeju',
  'Pangyo',
  'Seoul',
  'NewYork',
  'LA',
  'Jeju',
  'Pangyo',
  'Seoul',
  'NewYork',
  'LA',
]);

/*
cache hit => 1
cache miss => 5

inoutput ex) (3, ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"])
! miss        miss      miss        miss        miss        miss          miss
1 "Jeju"     "Jeju"     "Jeju"      "Pangyo"    "Seoul"     "NewYork"    "LA"
2            "Pangyo"   "Pangyo"    "Seoul"     "NewYork"   "LA"         "Jeju"
3                       "Seoul"     "NewYork"   "LA"        "Jeju"       "Pangyo"

! miss        miss
1 "Jeju"      "Pangyo"
2 "Pangyo"    "Seoul"
3 "Seoul"     "NewYork"

=> 10 * 5 = 50

inoutput ex) (3, ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"])
! miss    miss      miss    hit       hit       hit       hit       hit       hit
1 Jeju    Jeju      Jeju    Pangyo    Seoul     Jeju      Pangyo    Seoul     Jeju
2         Pangyo    Pangyo  Seoul     Jeju      Pangyo    Seoul     Jeju      Pangyo
3                   Seoul   Jeju      Pangyo    Seoul     Jeju      Pangyo    Seoul

=> 15 + 6 = 21

*/

저번 스터디 때 지원님이 Set 객체를 쓰신 것 보고 꼭 한 번 써 보고 싶어서 원래는 findindex를 사용해서 풀어보려고 하다가 index는 해당 인덱스 위치의 값을 삭제하기 까다로워서 Set을 이용해보자고 하고 성공시킨 코드이다 생각보다 다루기 간편해서 Set 나름 좋은 놈이구나...싶었다. 정처기 공부하면서 공부했던 교체 알고리즘도 다시 정리할 수 있었다. 이번 문제들은 대체적으로 유용한 문제들이 많아서 좋았다.