미고렝 코딩

문제

세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다.

입력

인자 1 : n

• number 타입의 1 이상의 자연수

출력

• number 타입을 리턴해야 합니다.

주의사항

• 타일을 가로, 세로 어느 방향으로 놓아도 상관없습니다. (입출력 예시 참고)

입출력 예시

let output = tiling(2);
console.log(output); // --> 2

output = tiling(4);
console.log(output); // --> 5
/* 
2 x 4 보드에 타일을 놓는 방법은 5가지
각 타일을 a, b, c, d로 구분

2 | a b c d
1 | a b c d 
------------

2 | a a c c
1 | b b d d 
------------

2 | a b c c
1 | a b d d 
------------

2 | a a c d
1 | b b c d 
------------

2 | a b b d
1 | a c c d 
------------
*/

Advanced

• 타일링 문제를 해결하는 효율적인 알고리즘(O(N))이 존재합니다. 반드시 직접 문제를 해결하시면서 입력의 크기에 따라 어떻게 달라지는지 혹은 어떻게 반복되는지 관찰하시기 바랍니다.

let tiling = function (n) {
	// TODO: 여기에 코드를 작성합니다.
	let count = 0;
	let ground = [];
	for (let i = 0; i < 2; i++) {
		//세로길이 2
		ground.push(new Array(n).fill(0));
	}
	//[0, 0, 0, 0, 0]
	//[0, 0, 0, 0, 0]
	//{1: [[0,0],[1,0]]} 1번 타일
	//{2: [[0,1],[1,1]]} or {2: [[0,1],[0,2]]} 2번 타일
	let find0 = function (changedField) {
		for (let i = 0; i < changedField.length; i++) {
			for (let j = 0; j < changedField[i].length; j++) {
				if (changedField[i][j] === 0) {
					return [i, j];
				}
			}
			//다 채워지면
		}
		return null;
	};
	//startIndex = find0(field)
	let putTile = function (field) {
		//가로로 넣어보기 --> x축에 +1
		if (find0(field) === null) {//필드가 다 채워지면			
			count++;
		} else {
			let [y, x] = find0(field);
			//세로로 넣어보기
			if (field[y + 1] !== undefined) {
				if (field[y + 1][x] === 0) {
					//세로로 놓아지는지 확인
					//let copyfield = field.slice();
					let copyfield = [];
					for (let row of field) {//2차원 배열을 복사할땐 이렇게 해야한다!!
						copyfield.push(row.slice());
					}
					copyfield[y][x] = 1;
					copyfield[y + 1][x] = 1;					
					putTile(copyfield);				
				}
			}
			if (field[y][x + 1] === 0) {
				//가로로 놓아지는지 확인
				let copyfield = [];
				for (let row of field) {
					copyfield.push(row.slice());
				}
				copyfield[y][x] = 1;
				copyfield[y][x + 1] = 1;
				putTile(copyfield); // 다음 타일 놓기
			}

			//넣고 재귀 돌리기
			//다 채워지면 count++
		}
	};
	putTile(ground);
	return count;
};

// naive solution: O(2^N)
// 2 x 4 보드에 타일을 놓는 방법은 5가지다.
// 각 타일을 a, b, c, d로 구분한다.
// 아직 타일이 놓이지 않는 부분은 -로 표기한다.
// 타일을 놓는 방법은 가장 왼쪽부터 세로로 놓거나 가로로 놓는 것으로 시작한다.
// 1) 세로로 놓는 법
//   2 | a - - -
//   1 | a - - -
//   ------------
// 2) 가로로 놓는 법
// 타일을 가로로 놓게 되면, 그 바로 아래에는 가로로 놓을 수 밖에 없다.
//   2 | a a - -
//   1 | b b - -
//   ------------
// 이때, 타일이 아직 놓이지 않은 부분은 사실 크기만 다를뿐 같은 종류의 문제라는 것을 알 수 있다.
// 즉, 2 x 4 보드에 타일을 놓는 방법은 아래 두 가지 방법을 더한 결과와 같다.
//  1) 2 x 3 보드에 타일을 놓는 방법
//  2) 2 x 2 보드에 타일을 놓는 방법
// 따라서 2 x n 타일 문제는 아래와 같이 재귀적으로 정의할 수 있다.
// 주의: 재귀적 정의에는 항상 기초(base), 즉 더 이상 재귀적으로 정의할 수 없는(쪼갤 수 없는) 문제를 별도로 정의해야 한다.
// let tiling = function (n) {
//   if (n <= 2) return n;
//   return tiling(n - 1) + tiling(n - 2);
// };

// dynamic with memoization: O(N)
let tiling = function (n) {
  // 인덱스를 직관적으로 관리하기 위해
  // 앞 부분을 의미없는 데이터(dummy)로 채운다.
  const memo = [0, 1, 2];

  // 재귀를 위한 보조 함수(auxiliary function)을 선언)
  const aux = (size) => {
    // 이미 해결한 문제는 풀지 않는다.
    if (memo[size] !== undefined) return memo[size];
    if (size <= 2) return memo[n];
    memo[size] = aux(size - 1) + aux(size - 2);
    return memo[size];
  };
  return aux(n);
};

// dynamic with tabulation: O(N)
// tabulation은 데이터를 테이블에 정리하면서 bottom-up 방식으로 해결하는 기법을 말합니다.
// let tiling = function (n) {
//   const memo = [0, 1, 2];
//   if (n <= 2) return memo[n];
//   for (let size = 3; size <= n; size++) {
//     memo[size] = memo[size - 1] + memo[size - 2];
//   }
//   return memo[n];
// };

// dynamic with slicing window: O(N)
// slicing window은 필요한 최소한의 데이터만을 활용하는 것을 말합니다.
// 크기 n의 문제에 대한 해결을 위해 필요한 데이터는 오직 2개뿐이라는 사실을 이용합니다.
// let tiling = function (n) {
//   let fst = 1,
//     snd = 2;
//   if (n <= 2) return n;
//   for (let size = 3; size <= n; size++) {
//     // 앞의 두 수를 더해 다음 수를 구할 수 있다.
//     const next = fst + snd;
//     // 다음 문제로 넘어가기 위해 필요한 2개의 데이터의 순서를 정리한다.
//     fst = snd;
//     snd = next;
//   }
//   return snd;
// };

문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

입력

인자 1 : n

• number 타입의 n (n은 0 이상의 정수)

출력

• number 타입을 리턴해야합니다.

주의사항

• 재귀함수를 이용해 구현해야 합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.

문제

김코딩은 몇 년의 해외 출장 끝에 본가에 내려왔습니다. 오랜만에 보는 김코딩의 얼굴에 반가웠던 부모님은 상다리가 부러질 정도로 음식을 만들었습니다. 감동의 재회도 잠시, 의자에 앉아 식사를 하려던 김코딩은 무엇부터 먹어야 될지 깊은 생각에 빠졌습니다. 정성스럽게 차려 주신 만큼, 최대한 많은 방법으로 다양하게 먹고 싶었기 때문입니다.

밥은 한 가지이며 반찬은 다수일 때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.

입력

인자 1: sideDishes

• String 타입의 영문으로 된 반찬이 나열되어 있는 배열

출력

• Array 타입을 리턴해야 합니다.
• 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수가 담긴 배열

주의사항

• 반찬은 영문으로 작성이 되어 있습니다.
• 반찬은 중복되지 않습니다.
• 반찬을 먹지 않는 것도 포함됩니다. (출력되는 2차원 배열은 빈 배열을 포함합니다.)
• 반찬은 3개 이상 99개 이하입니다.
• 출력되는 배열은 전부 사전식 순서(lexical order)로 정렬되어야 합니다. ex)

입출력 예시

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

문제

오늘은 빼빼로 데이입니다. 한 회사의 팀장은 출근길에 아몬드 빼빼로 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]] 
// 순서는 상관없습니다

문제

말썽꾸러기 김코딩은 오늘도 장난을 치다가 조별 발표 순서가 담긴 통을 쏟고 말았습니다.

선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.

김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤, 선생님께서 숫자를 말하면 그 순서에 맞는 경우의 수를 말해야 하고, 발표 순서를 말하면 이 발표순서가 몇번째 경우의 수인지를 대답해야 합니다.

총 학생의 수 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

문제

자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 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

문제

김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다.

예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.

박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.

짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.

입력

인자 1: stuff

• Number 타입의 40 이상 240 이하의 자연수를 담은 배열
  • ex) [70, 50, 80, 50]

인자 2: limited

• Number 타입의 40 이상 240 이하의 자연수

출력

• Number 타입을 리턴해야 합니다.
• 모든 짐을 옮기기 위해 필요한 박스 개수의 최솟값을 숫자로 반환합니다.

주의사항

• 옮겨야 할 짐의 개수는 1개 이상 50,000개 이하입니다.
• 박스의 무게 제한은 항상 짐의 무게 중 최대값보다 크게 주어지므로 짐을 나르지 못하는 경우는 없습니다.

입출력 예시

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

문제

1, 2, 3으로만 이루어진 수열 바코드를 만들어야 합니다. 무조건 1, 2, 3만 붙여서 바코드를 만들었다면 쉬웠겠지만, 아쉽게도 바코드를 만드는 데에 조건이 걸려 있습니다. 바코드에서 인접한 두 개의 부분 수열이 동일하다면 제작할 수 없다고 할 때, 주어진 길이 len의 바코드 중 가장 작은 수를 반환하는 함수를 작성하세요.

• 부분수열? 주어진 수열에서 연속된 모든 구간을 말합니다. 수열 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을 반환해야 합니다.

입출력 예시

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

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

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