스택과 재귀함수

괄호 유효성 검사

( { [ ] } ) => 괄호가 올바르게 닫혀있으면 true

({[ , ( , {{{ , (([]]] 등 => 괄호가 올바르게 닫혀있지 않으면 fasle

const isValid = (string) => {
  let stack = [];
  let pair = "";
  const paren_map = {
    ")": "(",
    "}": "{",
    "]": "["
  };
  for(const ch of string){
    if(!Object.keys(paren_map).includes(ch)){
      stack.push(ch);
    } else { 
      if(stack){
        pair = stack.pop();
      }
      if(paren_map[ch] !== pair){
        return false;
      }
    }
  }
  return stack.length === 0;
};

console.log(isValid("(([]]]")); // true

계단 오르기

꼭대기(n) 계단이 주어지면 오르는 방법의 가지수를 구하는 문제
ex) n=3 => 3개 (1+2, 2+1, 1+1+1)

function climbStairs(n){
  function climb(n,i){
    if(n===i){
      return 1;
    }
    if(n < i){
      return 0;
    }
    return climb(n, i+1) + climb(n, i+2);
  }
  return climb(n,0);
}

permutation

주어진 문자열을 재조합하는 모든 경우의 수

let result = [];
function find_permutation(list, idx, len){
  if(idx === len-1) {
    result.push(list.join());
  } else {
    let temp = "";
    for(let i=idx; i<len; i++){
      temp = list[idx];
      list[idx] = list[i];
      list[i] = temp;
      find_permutation(list, idx+1, len);
      temp = list[idx];
      list[idx] = list[i];
      list[i] = temp;
    }
  }
}
const str = "abc";
find_permutation(str.split(""), 0, str.split("").length);
console.log(result); // [ 'a,b,c', 'a,c,b', 'b,a,c', 'b,c,a', 'c,b,a', 'c,a,b' ]

동전 교환

가장 적은 동전의 개수를 반환
동전 배열(종류) [1, 2, 5], 거슬러줘야 하는 돈 11 => [5,5,1], 3개

function coinChange(coins, value){
  function change(v){
    if (v===0) return 0;
    let min_coin_cnt = Number.MAX_SAFE_INTEGER;
    for(const c of coins){
      if((v-c)>=0){
        const change_cnt = change(v-c);
        if(change_cnt < min_coin_cnt) min_coin_cnt = change_cnt;
      }
    }
    return min_coin_cnt + 1;
  }
  let answer = change(value);
  return answer !== Number.MAX_SAFE_INTEGER+1 ? answer : -1;
}
console.log(coinChange([1,2,5], 11)); // 3

배열의 두 부분집합의 최소 차이

배열을 두 부분집합으로 만들고 각각의 부분집합의 합 차이가 최소가 되는 값을 반환
[3,2,7,4,1] => [1,7], [2,3,4] => 8-9 => 1

let min_diff = Number.MAX_SAFE_INTEGER;
let total = 0;
function subset_diff(idx, nums, subsum){
  total = nums.reduce((a,c)=>(a+c));
  if (idx === nums.length){
    min_diff = Math.min(min_diff, Math.abs((total-subsum) - subsum));
    return;
  }
  subset_diff(idx+1, nums, subsum + nums[idx]);
  subset_diff(idx+1, nums, subsum);
}

subset_diff(0, [3,2,4,7,1], 0);
console.log(min_diff); // 1