- 말썽꾸러기 김코딩은 오늘도 장난을 치다가 조별 발표 순서가 담긴 통을 쏟고 말았습니다.
선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.
김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤 발표 순서를 말하면 이 발표 순서가 몇 번째 경우의 수인지를 대답해야 합니다.
총 조의 수 N과 선생님이 말씀하시는 발표 순서 k가 주어질 때, 김코딩이 정답을 말 할 수 있게 올바른 리턴 값을 구하세요.
모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다
ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
입출력 예시
let output = orderOfPresentation(3, [2, 3, 1]);
console.log(output); // 3
output = orderOfPresentation(5, [1, 3, 2, 4, 5])
console.log(output); // 6정답
function orderOfPresentation (N, K) {
// TODO: 여기에 코드를 작성합니다.
let answer = 0; // 몇 번째 발표 순서인지 담을 변수 선언
const fact = function(n) { // 경우의 수를 구하기 위한 팩토리얼 선언
if ( n <= 1) return 1
return n * fact(n-1)
}
const arr = Array(N+1).fill(false) // 배열을 생성하는데 N+1개의 false를 담고 있다. 이 배열은 모든 경우의 수(오름차순의 발표 순서)를 구하는 용도이다
//ex) N = 4 [false,false,false,false,false]
//배열의 갯수가 N+1인 이유는 조 갯수 N은 1부터 시작하고 배열 arr는 인덱스 0부터 시작하기 때문. 인덱스 0번째는 더미 데이터
for(let i=0; i<K.length; i++) { // 발표 순서를 담은 배열 K의 인자들을 탐색한다
const num = K[i] // C는 K[i]번째 인자의 값을 갖는다. ex) K[0] = 2
arr[num] = true // B의 num번째 인자 값을 true로 바꾼다. B[2] = true [false, false, true, false] >>
// 우리가 구하는건 모든 경우의 수 (== 오름 차순의 배열 순서) 중 몇번째 순서인지를 구하는 것이므로
// 우선 num번째 인자 앞에서 나올 수 있는 경우의 수를 구한다
const A = arr.slice(1, num) // 경우의 수를 구하기 위해 arr를 추출한다
const valid =A.filter((el) => el === false).length // 위의 과정에서 나올 수 있는 경우의 수와 팩토리얼 하기 위해 false 갯수를 추출한다
const before = valid * fact(N - i - 1) // 아직 나오지 않은 경우의 수를 계산한다. 0부터 시작하기에 -1을 빼준다
// N=5이고 K= [4,3,1,5,2]이고 위의 식을 진행해서 arr = [f, f, f, f, t, f] 일 때
//나오는 경우의 수는 4를 4번째 순서에 고정시키고 앞에 나올 수 있는 숫자 3가지와 남은 숫자 4를 조합시키는 것 즉 3 * 4!
answer = answer + before // 경우의 수 갯수를 누적시킨다
}
return answer // 최종적으로 몇번째인지 리턴한다
}2. 아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.
0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
피보나치 수열을 구하는 효율적인 알고리즘(O(N))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.
입출력 예시
let output = fibonacci(0);
console.log(output); // --> 0
output = fibonacci(1);
console.log(output); // --> 1
output = fibonacci(5);
console.log(output); // --> 5
output = fibonacci(9);
console.log(output); // --> 34
정답
function fibonacci(n) {
// TODO: 여기에 코드를 작성합니다.
const remember = [0, 1] // num이 같은 수가 들어왔을 때 재연산할 필요 없이 바로 추출할 수 있게 값을 기록해논다
const fibo = function(n){ // fibo라는 변수를 선언한다
if(remember[n] !== undefined){ // fibo는 기록장에 아직 n에 해당하는 값이 있으면
return remember[n] // 돌려준다
}
return remember[n] = fibo(n-1) + fibo(n-2) // 아닐 경우 연산해서 넣어준다
}
return fibo(n) // fibonacci(n) 함수는 fibo(n) 변수를 리턴한다
}3. 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다
시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과해 보세요.
입출력 예시
let base = [1, 2, 3, 4, 5];
let sample = [1, 3];
let output = isSubsetOf(base, sample);
console.log(output); // --> true
sample = [6, 7];
output = isSubsetOf(base, sample);
console.log(output); // --> false
base = [10, 99, 123, 7];
sample = [11, 100, 99, 123];
output = isSubsetOf(base, sample);
console.log(output); // --> false정답
const isSubsetOf = function (base, sample) {
// TODO: 여기에 코드를 작성합니다.
base.sort((a,b) => a-b) // 입력 인자 base를 오름차순으로 정렬
sample.sort((a,b) => a-b) // sample 역시 오름차순 정렬
const find = (item, arr, from) => { // 세 인자 받는 find 변수 선언
for (let i= from; i<arr.length; i++) { // 배열 길이만큼 주어진 수로부터 탐색하는 for문 선언
if(item === arr[i]) { // item이 arr의 i번째 인자라면
return i;} // i를 반환
}
return -1; // 디폴트로 -1 반환
}
let Idx = 0; // Idx 변수 선언하고 초기값은 0이다
for(let i=0; i<sample.length; i++) { // 샘플 배열의 길이만큼 루프를 돌린다
Idx = find(sample[i], base, Idx) // Idx는 0 ( Idx = 0 )부터 base.length만큼 루프를 반복해서 sample[i]와 base[j]가 매칭되는지 확인. 즉 for문 안의 for문 형태다
if (Idx === -1) {
return false // find 변수는 배열의 특정 인자와 매칭되지 않으면 -1, 매칭되면 이외의 숫자를 반환하므로 -1일 때 false 리턴
};
}
return true // 디폴트로 트루 반환
}4. 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다.
버블 정렬 알고리즘은 아래와 같습니다.
-
첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
-
두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
-
1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
-
1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
-
1~3의 과정을 첫 요소부터 다시 반복합니다.
-
5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
-
1~3의 과정을 총 n번(배열의 크기) 반복합니다.
이 모습이 마치 '거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부릅니다.
입출력 예시
let output = bubbleSort([2, 1, 3]);
console.log(output); // --> [1, 2, 3]정답
const bubbleSort = function (arr) {
// TODO: 여기에 코드를 작성합니다.
const swap = function (idx1, idx2, arr) { ///변수 swap은 idx1,idx2, arr 세개의 인풋을 받는 함수다
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]; // swap은 idx1과 idx2의 위치를 바꾼다
}
for(let i=0; i< arr.length -1; i++) { // 마지막 전 요소와 마지막 요소가 비교되면 끝나기 때문에 arr.length - 1 까지만 실행한다
let num = 0; // 스왑 횟수를 기록하기 위한 num 선언
for (j=0; j<arr.length -1 - i; j++) { // i가 증가함에 따라 배치 필요 요소가 하나씩 줄어듦으로 루프 범위는 arr.length - 1 - i로 한다
if(arr[j] > arr[j+1]) { // arr[j]번째 요소를 뒷 요소와 비교 후
num ++ // 스왑 증가를 기록
swap (j, j+1, arr) // 부합하면 뒤로 보낸다
}
}
if ( num === 0 ) { // 스왑 횟수가 0이면 ( 오름차순 정배열이면)
return arr // 배열 조정을 멈추고 배열을 반환한다
}
}
return arr // 배열 조정이 끝나면 리턴한다
};
5. 세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다
입출력 예시
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
------------
정답
let tiling = function (n) {
// TODO: 여기에 코드를 작성합니다.
const A = [0, 1, 2];
const B = (num) => {
if(A[num] != undefined) { // 해당 인자가 없으면
return A[num] // undefined 반환
}
else if (num <= 2) {
return A[num]
} // 인덱스 크기가 2 이하이면 A[b] 리턴
A[num] = B(num-1) + B(num-2) // B가 인자로 받는 숫자를 배열 A의 인덱스에 대입하여 값을 비교해보고 값이 없을 때, 2이하일 때 그 외의 경우 재귀로 처리
return A[num] // 재귀로 계산된 A[num] 리턴
}
return B(n) // tiling(n)은 함수 B(n)을 반환한다
};- 스도쿠는 숫자 퍼즐로, 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐입니다.
퍼즐을 푸는 방법은 아홉 가로줄, 세로줄, 3X3 칸에 1에서 9까지의 숫자를 중복되지 않게 한 번씩만 넣으면 됩니다.
일부 칸이 비어있는 상태인 스도쿠 보드를 입력받아 스도쿠 퍼즐이 완성된 보드를 리턴해야 합니다
입출력 예시
let board = [
[0, 3, 0, 2, 6, 0, 7, 0, 1],
[6, 8, 0, 0, 7, 0, 0, 9, 0],
[1, 9, 0, 0, 0, 4, 5, 0, 0],
[8, 2, 0, 1, 0, 0, 0, 4, 0],
[0, 0, 4, 6, 0, 2, 9, 0, 0],
[0, 5, 0, 0, 0, 3, 0, 2, 8],
[0, 0, 9, 3, 0, 0, 0, 7, 4],
[0, 4, 0, 0, 5, 0, 0, 3, 6],
[7, 0, 3, 0, 1, 8, 0, 0, 0],
];
let output = sudoku(board);
console.log(output); // -->
/*
[
[4, 3, 5, 2, 6, 9, 7, 8, 1],
[6, 8, 2, 5, 7, 1, 4, 9, 3],
[1, 9, 7, 8, 3, 4, 5, 6, 2],
[8, 2, 6, 1, 9, 5, 3, 4, 7],
[3, 7, 4, 6, 8, 2, 9, 1, 5],
[9, 5, 1, 7, 4, 3, 6, 2, 8],
[5, 1, 9, 3, 2, 6, 8, 7, 4],
[2, 4, 8, 9, 5, 7, 1, 3, 6],
[7, 6, 3, 4, 1, 8, 2, 5, 9],
];
*/
정답
const sudoku = function (board) { // sudoku 함수의 큰 흐름은 for문 2개 실행 이후 하단의 aux 조건에 따라 완성된다
// TODO: 여기에 코드를 작성합니다.
const N = board.length;
const boxes = [
[0, 0, 0, 1, 1, 1, 2, 2, 2],
[0, 0, 0, 1, 1, 1, 2, 2, 2],
[0, 0, 0, 1, 1, 1, 2, 2, 2],
[3, 3, 3, 4, 4, 4, 5, 5, 5],
[3, 3, 3, 4, 4, 4, 5, 5, 5],
[3, 3, 3, 4, 4, 4, 5, 5, 5],
[6, 6, 6, 7, 7, 7, 8, 8, 8],
[6, 6, 6, 7, 7, 7, 8, 8, 8],
[6, 6, 6, 7, 7, 7, 8, 8, 8],
];
const getBoxNum = (row, col) => boxes[row][col]; // getBoxNum은 boxes의 인자 정보를 담고 있다.
const blanks = [];
const rowUsed = [];
const colUsed = [];
const boxUsed = [];
for (let row = 0; row < N; row++) {
rowUsed.push(Array(N + 1).fill(false)); // [Array(10), Array(10), Array(10), Array(10), Array(10), Array(10), Array(10), Array(10), Array(10)]
colUsed.push(Array(N + 1).fill(false)); // ""
boxUsed.push(Array(N + 1).fill(false)); // "" false 10개가 채워진 Array를 9개 생성 ( 10 * 9)
}
for (let row = 0; row < N; row++) {
for (let col = 0; col < N; col++) {
if (board[row][col] === 0) {
blanks.push([row, col]); // 받아온 보드의 행과 열을 탐색해 0인 인자의 행열 좌표를 blanks에 담는다
} else { // 인자가 0이 아니면
const num = board[row][col]; // board의 인자를 추출하는 num. board[row][col]이 0이 아닐 때 num이 존재
const box = getBoxNum(row, col); // 표준 폼 boxes의 인자를 추출하는 box
rowUsed[row][num] = true; // [행][인자값] >> true
colUsed[col][num] = true; // [열][인자값] >> true
boxUsed[box][num] = true; // [box][인자값] >> true
}
}
}
const isValid = (row, col, num) => {
const box = getBoxNum(row, col); // box = getBoxNum(row, col) = boxes[row][col]
return (
rowUsed[row][num] === false &&
colUsed[col][num] === false &&
boxUsed[box][num] === false
); // 행, 열, 박스 모두에서 false일 때 true를 리턴
};
const toggleNum = (row, col, num) => {
const box = getBoxNum(row, col);
board[row][col] = num; // board의 인자에 num 값 삽입
rowUsed[row][num] = !rowUsed[row][num];
colUsed[col][num] = !colUsed[col][num];
boxUsed[box][num] = !boxUsed[box][num]; // boolean 값 뒤집는다
};
const aux = (idx, blanks, board) => { // aux는 세 인자를 받는다.
if (idx === blanks.length) { // idx가 blanks 배열 길이와 같으면
return true; // true 리턴. 아래 인덱스를 0을 넣었으니 blanks가 빌 때 리턴 트루 나옴
}
// 블랭스가 채워져있으면
const [row, col] = blanks[idx]; // blanks[0]의 행열 좌표 가져온다. blanks[idx]는 board의 0 인자 좌표를 갖고 있고 그것을 가져온다.
for (let num = 1; num <= 9; num++) { // num을 1부터 9까지 루프 실행
if (isValid(row, col, num) === true) { // (rowUsed[row][num] === false && colUsed[col][num] === false && oxUsed[box][num] === false) 가 true라면
toggleNum(row, col, num); // toggleNum, 보드에 num을 삽입하고 boolean 값을 뒤집는다. 각 요소 값을 true로 바꿈.
if (aux(idx + 1, blanks, board) === true) { // 재귀 함수 사용해서 다음 인덱스 번호를 비교하고 true면 ex) idx : 24 blanks.length = 24
return true; // 루프 종료
}
toggleNum(row, col, num); // true가 나올 때까지 num을 삽입
}
}
return false; // 디폴트는 false
};
aux(0, blanks, board); // aux에 0을 시작으로 완성되면 보드를 리턴한다
return board;
};
7. 임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다.
이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다
입출력 예시
let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = dfs(root);
console.log(output); // --> [1, 2, 4, 5, 3]
leaf1.addChild(new Node(6));
rootChild2.addChild(new Node(7));
output = dfs(root);
console.log(output); // --> [1, 2, 4, 6, 5, 3, 7]정답
let dfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
let val = [node.value] // 노드의 속성값을 담는 변수 val
node.children.forEach((n) => { // 노드의 자식 인자들을 순회시킨다
val = val.concat(dfs(n)) // 노드의 속성값들을 삽입하는 재귀함수를 사용한다
})
return val
};
// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
this.value = value;
this.children = [];
};
// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};8. 정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴해야 합니다
입출력 예시
let output = largestProductOfThree([2, 1, 3, 7]);
console.log(output); // --> 42 (= 2 * 3 * 7)
output = largestProductOfThree([-1, 2, -5, 7]);
console.log(output); // --> 35 (= -1 * -5 * 7)정답
const largestProductOfThree = function (arr) {
// TODO: 여기에 코드를 작성합니다.
const sorted = arr.slice().sort((a, b) => a - b); // arr의 원본을 복사한 후(slice) 오름 정렬
const len = arr.length;
const candi1 = sorted[len - 1] * sorted[len - 2] * sorted[len - 3]; // 오름 정렬한 배열의 마지막에서 3번째 인자까지 곱해준다
const candi2 = sorted[len - 1] * sorted[0] * sorted[1]; // 마지막 인자, 첫번째, 두번째 인자를 곱한다
return Math.max(candi1, candi2); // 2개의 인자를 비교하여 큰 값을 반환하는 메서드 Math.max 사용
};
9. 두 수를 입력받아 거듭제곱을 리턴해야 합니다
Math.pow, 거듭제곱 연산자 사용은 금지됩니다.
시간복잡도 O(logN)을 만족해야 합니다.
나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 안 됩니다. 연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가시기 바랍니다.
입출력 예시
let output = power(3, 40);
console.log(output); // --> 19334827정답
function power(base, exponent) {
// todo: 여기에 코드를 작성합니다.
if (exponent === 0) return 1;
const half = parseInt(exponent / 2); // 거듭제곱 값을 절반으로 나눈다
const temp = power(base, half); // 나눈 인자를 받는 재귀형태로 만들어준다
const result = (temp * temp) % 94906249; // 재귀 형태로 곱해준다
if (exponent % 2 === 1) return (base * result) % 94906249; // 홀수일 경우 거듭 제곱값을 절반으로 나눴을 때 한 번이 모자라게 곱해지기에 base를 한 번 더 곱해준다
else return result; // 짝수면 그냥 리턴
}
10. 오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다
이진탐색 알고리즘(O(logN))을 사용해야 합니다.
단순한 배열 순회(O(N))로는 통과할 수 없는 테스트 케이스가 존재합니다.
target이 없는 경우, -1을 리턴해야 합니다.
입출력 예시
let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
console.log(output); // --> 2
output = binarySearch([4, 5, 6, 9], 100);
console.log(output); // --> -1정답
const binarySearch = function (arr, target) {
// TODO : 여기에 코드를 작성합니다.
let left = 0,
right = arr.length - 1; // 인덱스 참조를 위해 총 길이 - 1
while (left <= right) { // left가 right 이하가 될 때까지 반복
let middle = parseInt((right + left) / 2); // 소수점 이하를 제거하기 위한 parseInt. 탐색을 위한 인덱스 설정
if (arr[middle] === target) { // 타겟과 매칭된다면 미들 리턴
return middle;
}
if (target < arr[middle]) { // 타깃이 중간인덱스의 숫자보다 작으면 right을 줄인다
right = middle - 1;
} else { // // 타깃이 중간인덱스의 숫자보다 크면 left를 높인다
left = middle + 1;
}
}
return -1; // 해당되는 target이 없는 경우 -1 리턴
};
세상은 넓고 배울건 많다