김코딩은 몇 년의 해외 출장 끝에 본가에 내려왔습니다. 오랜만에 보는 김코딩의 얼굴에 반가웠던 부모님은 상다리가 부러질 정도로 음식을 만들었습니다. 감동의 재회도 잠시, 의자에 앉아 식사를 하려던 김코딩은 무엇부터 먹어야 될지 깊은 생각에 빠졌습니다. 정성스럽게 차려 주신 만큼, 최대한 많은 방법으로 다양하게 먹고 싶었기 때문입니다.
밥은 한 가지이며 반찬은 다수일 때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.
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();
}
오늘은 빼빼로 데이입니다. 한 회사의 팀장은 출근길에 아몬드 빼빼로 A 개와 누드 빼빼로 N 개를 구매하여 아침 일찍 출근길에 나섰습니다.
팀장은 자신보다 먼저 출근해있는 직원들에게 빼빼로를 모두 나누어 주려고 합니다. 단, 직원들이 서로 같은 개수의 빼빼로를 받지 못하면 시기 질투할 수 있으므로 직원들에게 같은 개수를 나누어 주어야 하며, 한 가지 종류의 빼빼로만 받는 경우가 없어야 합니다.
회사에 도착하기 전이기 때문에 이미 출근해 있는 직원들이 몇 명인지 모르는 상황입니다. 예를 들어, 팀장이 아몬드 빼빼로를 4개, 누드 빼빼로를 8개를 구매 했다면, 다음과 같이 세 가지 방법으로 나누어 줄 수 있습니다.
출근한 직원이 1명이라면 아몬드 빼빼로 4개와 누드 빼빼로 8개를 줄 수 있습니다.
출근한 직원이 2명이라면 아몬드 빼빼로 2개와 누드 빼빼로 4개를 각각 줄 수 있습니다.
출근한 직원이 4명이라면 아몬드 빼빼로 1개와 누드 빼빼로 2개를 각각 줄 수 있습니다.
팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다. 여러분이 직원 수에 따라 빼빼로를 나누어 주는 방법을 구하는 솔루션을 제공해 주세요.
입력
인자 1: A
Number 타입의 아몬드 빼빼로 개수
인자 2: N
Number 타입의 누드 빼빼로 개수
출력
직원 수에 따라 각각 빼빼로를 나누어 주는 방법을 다음과 같은 순서로 배열에 담아야 합니다.
Number 타입의 요소
[빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]
위와 같은 방법들을 순서에 상관없이 배열에 담아 출력해야 합니다.
주의사항
1 ≤ A, N ≤ 1,000,000,000 (A는 구매한 아몬드 빼빼로 개수, N은 구매한 누드 빼빼로 개수 )
TIP : 위 범위와 가까운 최대 공약수인 경우, 모든 최대 공약수의 약수를 탐색하는 것은 비효율적 입니다. 제곱근을 활용할 수 있어야 합니다.
36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 입니다. 36의 제곱근 6을 기준으로 이하 약수를 통해 모든 약수를 구할 수 있습니다.
1 x 36 = 2 x 18 = 3 x 12 = 4 x 9 = 6 x 6 = 36 입니다.
입출력 예시
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;
}
선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.
김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤, 선생님께서 숫자를 말하면 그 순서에 맞는 경우의 수를 말해야 하고, 발표 순서를 말하면 이 발표순서가 몇번째 경우의 수인지를 대답해야 합니다.
총 학생의 수 N과 선생님이 말하는 k가 주어질 때, 김코딩이 정답을 말 할 수 있게 올바른 리턴 값을 구하세요.
모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다. ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
입력
인자 1: n
Number 타입의 1 <= N <= 20인 조의 갯수
인자 2: k
k가 Number 일 때, k번째 배열을 리턴합니다.
ex) n이 3이고 k가 3일 경우
모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,
반환하는 값은 [2, 3, 1]이 됩니다.
k가 Array일 때, 몇 번째인지를 리턴합니다. (0 <= index 입니다.)
ex) n이 3이고 k가 [2, 3, 1]일 경우
모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,
반환하는 값은 3이 됩니다.
주의사항
k내에 중복되는 요소는 없다고 가정합니다.
입출력 예시
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]
}
}
자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.
예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.
$50 한 장을 훔친다
$20 두 장, $10 한 장을 훔친다
$20 한 장, $10 세 장을 훔친다
$10 다섯 장을 훔친다
훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.
입력
인자 1: target
Number 타입의 100,000 이하의 자연수
인자 2: type
Number 타입을 요소로 갖는 100 이하의 자연수를 담은 배열
출력
Number 타입을 리턴해야 합니다.
조지가 target을 훔칠 수 있는 방법의 수를 숫자로 반환합니다.
주의사항
모든 화폐는 무한하게 있다고 가정합니다.
입출력 예시
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];
}
1, 2, 3으로만 이루어진 수열 바코드를 만들어야 합니다. 무조건 1, 2, 3만 붙여서 바코드를 만들었다면 쉬웠겠지만, 아쉽게도 바코드를 만드는 데에 조건이 걸려 있습니다. 바코드에서 인접한 두 개의 부분 수열이 동일하다면 제작할 수 없다고 할 때, 주어진 길이 len의 바코드 중 가장 작은 수를 반환하는 함수를 작성하세요.
만들 수 없는 바코드만들 수 있는 바코드
112
1312
1231312
3
232312
231213
부분수열? 주어진 수열에서 연속된 모든 구간을 말합니다. 수열 123의 부분수열은 1, 2, 3, 12, 23, 123 입니다.
인접한 두 부분수열? 첫번째 부분수열과 두번째 부분수열이 연속된 경우를 말합니다.
수열 1234에서 인접한 부분수열 (우리는 두 부분수열이 같은 지 관심이 있으므로 길이가 서로 다른 경우는 무시한다)
1과 2, 2와 3, 3과 4, 12와 34입니다.
만들 수 없는 바코드를 보자면,
'11'2
12'3131'2
'2323'12 인접한 두 개의 부분 수열이 동일하기 때문에 만들 수 없습니다. 고로, '12131213'과 같이 네 자리씩 중복되어도 만들 수 없습니다. 자릿수와 상관없이, 인접한(붙어있는) 부분수열이 같다면 바코드를 만들 수 없습니다.
입력
인자 1: len
Number 타입의 1 이상 50 이하의 자연수
출력
String 타입을 리턴해야 합니다.
예시로, 121도, 123도 전부 바코드로 제작할 수 있지만 제일 작은 수는 121이기 때문에 121을 반환해야 합니다.
function connectedVertices(edges) {
let result = []
for(let edge of edges){
//result: [[0,1],[2,3]]
//edge : 3,4
let li = edge
let flag = false;
//toDo
for(let el of result){
//el: [2,3]
if(el.includes(edge[0]) || el.includes(edge[1])){
flag = true
if(el.includes(edge[0])){
el.push(edge[1])
}
else{
el.push(edge[0])
}
}
}
if(flag === false){
result.push(li)
}
}
let combine = function(arr){
let result = []
for(let i =0; i<arr.length; i++){
let nextArr = arr[i+1] || []
let flag= false;
for(let j=0;j<nextArr.length;j++){
if(arr[i].includes(nextArr[j])){
flag = true
}
}
if(flag){//포함이 되있다.
result.push(arr[i].concat(nextArr))//서로 포함관계인 두 요소를 합치고
arr[i + 1] = arr[i+2] //합쳐졌으니 자리를 옮겨준다
result = combine(result) //포함이 있는지 다시 확인. 있다면 다시 포함.없으면 그대로
}else{
result.push(arr[i])
if(i === arr.length-1 && nextArr.length >= 1){
result.push(nextArr)
}
}
}
return result
}
let result2 = combine(result)
let tempArr = result2.slice()
for(let el of tempArr){
if(el === undefined){
result2.pop()
}
}
return result2.length
}