미고렝 코딩

function fibonacci(n, memo = []) {
  // TODO: 여기에 코드를 작성합니다.
   if(memo[n] !== undefined) return memo[n];
		// 이미 해결한 하위 문제인지 찾아본다
    if(n === 0) return 0
    if(n <= 2) return 1;
    let res = fibonacci(n-1, memo) + fibonacci(n-2, memo);
		// 없다면 재귀로 결과값을 도출하여 res 에 할당
    memo[n] = res;
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
    return res;
}

let output = missHouseMeal(["eggroll", "kimchi", "fishSoup"]);
console.log(output);
/*
[ [], 
  [ 'eggroll' ], 
  [ 'eggroll', 'fishSoup' ], 
  [ 'eggroll', 'fishSoup', 'kimchi' ], 
  [ 'eggroll', 'kimchi' ], 
  [ 'fishSoup' ], 
  [ 'fishSoup', 'kimchi' ], 
  [ 'kimchi' ]
] 
*/

function missHouseMeal(sideDishes) {

  // 결과를 담을 배열을 선언합니다.
  let result = [];
  // sideDishes를 사전식 순서로 정렬합니다.
  sideDishes.sort();

  // 모든 조합을 검사하는 재귀 함수를 작성합니다.
  const sidePowerSet = (idx, sideDish) => {

    // 재귀 함수이기 때문에 탈출 조건을 만듭니다.
    if (idx === sideDishes.length) {
      // 만약, idx와 sideDishes의 길이가 같다면(마지막까지 검토한 경우) result에 sideDish를 삽입하고 push합니다.
      result.push(sideDish);
      return;
    }

    // idx번째 요소가 포함되지 않는 경우
    sidePowerSet(idx + 1, sideDish);

    // idx번째 요소가 포함되는 경우
    sidePowerSet(idx + 1, [...sideDish, sideDishes[idx]]);
  };

  // 0 번째 인덱스와 빈 배열을 인자로 받는 재귀 함수를 실행합니다.
  sidePowerSet(0, []);

  // 결과를 사전식 순서로 정렬합니다.
  return result.sort();
}

let A = 4;
let N = 8;

let output = divideChocolateStick(A, N);
console.log(output) 
// [[1, 4, 8], [4, 1, 2], [2, 2, 4]] 또는,
// [[1, 4, 8], [2, 2, 4], [4, 1, 2]] 
// 순서는 상관없습니다

// 최대 공약수(유클리드 호제법: Euclidean algorithm)
function gcd(A, N) {
     return (A % N) === 0 ? N : gcd(N, A % N); 
}

function divideChocolateStick(A, N) {
    const result = [];
    let value = 0; // 최대공약수를 담을 변수
    let temp = 0; //

    if(A > N) value = gcd(A, N); // A가 N보다 큰 경우
    else value = gcd(N, A); // N이 A보다 큰 경우

    // 제곱근 까지만 반복해도 된다.
    // 최대 공약수가 36이라면 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이다.
    // 이는 1 * 36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6 이다.
    // 즉, 제곱근을 기준으로 양쪽의 값 하나씩 곱했을 때 36이 되기 때문에
    // 제곱근 보다 큰 약수는 이미 제곱근보다 작은 약수에서 구할 수 있다.
    // 따라서 제곱근까지만 비교해 주면 된다.
    for(let i = 1; i * i <= value; i++) {
        if(value % i === 0) { // 최대공약수의 약수인 경우 중 제곱근 보다 작은 약수의 경우
            result.push([i, A / i, N / i]);
            if(i !== value / i) { // 제곱근이 아닌 경우(제곱근 보다 작은)
                temp = value / i; // 최대 공약수를 제곱근이 아닌 수로 나누면 제곱근 보다 큰 약수를 구할 수 있다.
                result.push([temp, A / temp, N / temp]);
            }
        }
    }
    
    return result;
}

let output = orderOfPresentation(3, 3);
console.log(output); // [2,3,1]

let output = orderOfPresentation(3, [2, 3, 1]);
console.log(output); // 3

function orderOfPresentation(n, k) {
  // TODO: 여기에 코드를 작성합니다.
  let numbers = []
  for(let i = 1; i<=n ; i++){
    numbers.push(i)
  }
  //obj에다가 key를 경우의 수로 두고 value를 boolean으로 줘서 이미 사용했던 숫자인지 판별
  //만들었던 숫자이면 for문 안에서 numbers의 인덱스를 올려서 숫자 조합하기.
  //n이 몇이 될지 모르니까 재귀를 통해서 구현해야한다.
  //조합한 숫자는 result에 담고 obj에 키로 추가
   //사용했던 카드의 정보를 담아야한다
  
  let result = []
  // let rec = (obj = {} ,combinated = '') =>{
  //   for(let i = 0; i < numbers.length; i++){//카드들을 순회   
  //     //카드를 선택하기전에 사용가능한 카드인지 확인         
  //     if(obj[numbers[i]] === true || obj[numbers[i]] === undefined){//사용 가능한 카드
  //       combinated += numbers[i]//카드를 선택하고
  //       obj[numbers[i]] = false //사용했던 카드로 표시
  //       console.log('combinated: ', combinated)
  //       console.log('obj[numbers[i]]: ', obj[numbers[i]])

  //       //그다음 카드를 선택하기 위해 재귀
  //       if(combinated.length < n){
  //         console.log("재귀-----------")
  //         combinated = rec(obj,combinated)
          
  //       }
  //       else{//카드가 다 만들어지면 체크 
  //       let strArr = combinated.split('')
  //       let numArr = strArr.map((el)=>Number(el))
  //       //result에 넣기전에 숫자로 변환시키기
  //       result.push(numArr)              
  //       console.log('result: ', result)
  //       }
  //       combinated = combinated.slice(0,-1) //다음 숫자 확인을 위해 썼던거 뺴주기
  //       obj[numbers[i]] = true //재귀가 끝났으니 다시 사용 가능하게 해줌
  //     }
  //     console.log("obj: ", obj)
  //     console.log('end of for loop @@@@@@@@@@@@@@@@@@@@')
            
  //   }    
  //   return combinated
  // }
  // rec()
  //위의 코드는 나의 코드인데 아래 코드처럼 순회해야하는 배열 자체를 줄여주면 더 효율적으로 순회할 수 있다
  const permutation = (arr, m = []) => {
    // 탈출 조건을 생성합니다.
    // arr의 length가 0일 때 result에 만들어진 발표 순서 배열을 담습니다.
    if (arr.length === 0) {
      result.push(m);
    } else {

      // 순열의 재료가 담긴 배열을 순환합니다.
      for (let i = 0; i < arr.length; i++) {
        // 현재 배열을 카피합니다. (원본을 건드리면 모든 경우의 수를 찾을 수 없습니다.)
        let currentArray = arr.slice();
        // 제일 앞에 있는 요소를 가지고 와서 변수에 할당합니다.
        let element = currentArray.splice(i, 1);
        // 제일 앞에 있는 요소가 사라진 배열 ([1, 2, 3]이었다면 현재는 [2, 3])을 arr 인자에 넣고, m 배열과 element를 합쳐서 m 인자에 넣습니다.
        permutation(currentArray.slice(), m.concat(element));

        // 이렇게 되면 다음은 [2, 3]을 카피하고, element가 [2]가 될 것이며
        // 제일 앞에 있는 요소가 사라진 배열 [3]이 arr에 들어갈 것이고, element는 m과 다시 합쳐져 [1, 2]를 만들 것입니다.
        // 이렇게 계속 재귀를 돌려서 m이 [1, 2, 3]이 되면, arr의 lenght는 0이 될 것이고, 재귀에서 빠져나옵니다.
        // arr === []일 때(m이 [1, 2, 3]) result에 push를 하여 함수를 종료하고, 그다음 arr === [3]일 때(m이 [1, 2]) for문의 길이가 1이었으므로 함수를 그대로 종료하고,
        // arr === [2, 3]일 때(m이 [1]) for문은 arr.length에 따라 2번 돌기 때문에 2를 지나 3이 될 것입니다.
        // [1] => [1, 3] => [1, 3, 2] => (1의 모든 경우의 수를 다 돌았으니 2로 진입) [2] => [2, 1] => [2, 1, 3] ...
      }
    }
  };

  permutation(numbers);
  console.log('final result: ', result)
  //리턴
  if(Array.isArray(k)){
    return result.findIndex((el)=>{
      return String(el) === String(k)
    })    
  }else{
    return result[k]
  }
}

let output = ocean(50, [10, 20, 50]);
console.log(output); // 4

let output = ocean(100, [10, 20, 50]);
console.log(output); // 10

let output = ocean(30, [5, 6, 7]);
console.log(output); // 4

// function ocean(target, type) {
//   // TODO: 여기에 코드를 작성합니다.
//   let sorted = type.sort((a,b)=>a-b)
//   let count = 0
//   let calledCount = 0
//   let rec = function(sum = 0, curr= sorted[0]){
//     calledCount++;
//     for(let i =0;i<sorted.length; i++){      
//       if(sorted[i] >= curr){//자신보다 크거나 같을 때만
//         if(sum + sorted[i] < target){ //아직 target에 미치지 못함
//           //rec(sum + sorted[i], sorted[i])
//         }
//         else if(sum + sorted[i] === target){
//           console.log('target에 도달')
//           console.log('sum: ', sum)
//           console.log('curr: ', curr)
//           console.log('sorted[i]: ', sorted[i])          
//           count++ //target에 도달
//         }
//       }
//     }
//   }
//   rec()
//   console.log('calledCount',calledCount)
//   return count
// }
//내가 한 위의 방법은 시간복잡도가 높아 5천이상만 되도 시간이 오래걸린다.

function ocean(target, type) {
  // 0 을 만들 수 있는 경우는 아무것도 선택하지 않으면 되기 때문에 bag[0] = 1 로 초기값 설정
  let bag = [1];
  // 경우의 수를 저장하기 위해 초기값은 모두 0으로 만들어 준다
  for(let i = 1; i <= target; i++)
    bag[i] = 0;
  // 돈의 종류가 담겨있는 배열을 순차적으로 탐색   
  for(let i = 0; i < type.length; i++) {
  // target 금액까지 순차적으로 1씩 증가하면서    
    for(let j = 1; j <= target; j++)
  // bag의 인덱스가 type[i] 보다 큰 구간만
  // (작은 구간은 type[i]로 만들 수 없는 금액이기 때문에 탐색할 필요가 없다)    
      if(type[i] <= j)
  // 기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해준다     
  // 정말 이런식의 풀이 방법은 어떻게 생각해 내는걸까....  
        bag[j] += bag[j-type[i]];
  }
  // bag 의 target 인덱스에 target 금액을 훔칠 수 있는 경우의 수가 쌓이므로
  // 해당 값을 리턴해 준다
  return bag[target];
}

let output = movingStuff([70, 50, 80, 50], 100);
console.log(output); // 3

let output = movingStuff([60, 80, 120, 90, 130], 140);
console.log(output); // 4

function movingStuff(stuff, limit) {
  let lineUpArr = stuff.sort(function(a, b)  {
  if(a > b) return 1;
  if(a === b) return 0;
  if(a < b) return -1;
  })
  let count = 0;
  let checkObj = {}
  for(let i = 0; i < stuff.length; i++){
    checkObj[i] = true
  }
  // 모두 true인 객체
  for(let i = 0; i < lineUpArr.length; i++){
    if(checkObj[i]){
      for(let j = lineUpArr.length - 1; j >= 0; j--){           
      if(checkObj[i] && checkObj [j] && i !== j){
        if(lineUpArr[i] + lineUpArr[j] <= limit){
          checkObj[i] = false;
          checkObj[j] = false;
          count++
          break;
        } 
      }
      else{
        if(j === 0 && i !== j){
          checkObj[i] = false;
          count++
        }
      } 
    }
    }
    
  }
  return count
}

Number()함수가 큰 숫자를 다룰 때는 조심해야한다. 64비트 이상의 숫자 (18,446,744,073,709,551,615)를 다루게 될때 (거의 알고리즘에서 밖에 다루지 않겠지만...) 서로 다른 숫자를 같은 숫자로 인식하는 등 여러가지 문제점이 발생한다.

따라서 큰 숫자를 다룰때는 String 타입으로 변환 시킨 다음 비교를 하던지 하자!

let output = barcode(3);
console.log(output); // "121"

output = barcode(7);
console.log(output); // "1213121"

output = barcode(20);
console.log(output); // "12131231321231213123"

function barcode(len) {
  // TODO: 여기에 코드를 작성하세요.
  //len만큼 문자열에 숫자를 추가한다.
  //len이 2이면 '1'+'1' 해보고 check돌려서 true가 나오면 '1'+'2'를 해본다
  //len이 3이면 '11' '12' '121'
  //len이 4이면 '11' '12' '121' '1211' '1212' '1213
  let visited = {}
  let result= ''  
  result = makeCode(result, len, visited)
  console.log(visited)
  return result
  
}
function makeCode(code, len,visited,i =1){
  if(code.length < len){
    if(i > 3){
      let lastNum = code.slice(-1)            
      code = makeCode(code.slice(0,-1), len,visited, Number(lastNum) + 1)
    }
    for(; i<= 3 ; i++){
      code += String(i)      
      if(check(code, visited)){//만들수 없는 바코드
        code = code.slice(0,-1)//마지막꺼를 다시 뺌
        if(i === 3){ //3까지 시도를 해봤지만 전부 안됐음
          let lastNum = code.slice(-1)            
          code = makeCode(code.slice(0,-1), len, visited, Number(lastNum) + 1)
        }   
      }      
      else{//만들수 있는 바코드
        break;
      }      
    }
    return makeCode(code, len,visited, 1)
  }
  return code
}
function check(str, visited){
  //let str = String(num)
  if(visited[str] === undefined){
    let reversed = str.split('').reverse().join('');
    let halfLength = Math.floor(reversed.length /2) 
    for(let i= 1; i <= halfLength; i ++){
      if(reversed.slice(0,i)=== reversed.slice(i, i+i)){
        visited[str] = true
        return true//같은게 있다
      }
    }    
    visited[str] = false
    return false
  }
  else{//방문 했던 곳
    return visited[str]
  }
}

주의할것: migoreng.tistory.com/110