코테/코드스테이츠[JS]
Toy 문제 7
문제 임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다. 입력 인자 1 : node 'value', 'children' 속성을 갖는 객체 (Node) 'node.value'는 number 타입 'node.children'은 Node를 요소로 갖는 배열 주의사항 생성자 함수(Node)와 메소드(addChild)는 변경하지 않아야 합니다. 입출력 예시 let root = new Node(1); let rootChild1 = root.addChild(new Node(2)); let rootChild2 = root.addChild(..
Toy 문제 6 sudoku
문제 스도쿠는 숫자 퍼즐로, 가로 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,..
Toy 문제 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 ------------ 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 ------------..
Toy 문제 4
문제 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다. 해석(수도코드) 버블 정렬 알고리즘은 아래와 같습니다. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap) 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap) 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교) 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다. 1~3의 과정을 첫 요소부터 다시 반복합니다. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 ..
Toy 문제3
문제 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 boolean 타입으로 리턴해야 합니다. base, sample 내에 중복되는 요소는 없다고 가정합니다. let base = [1, 2, 3, 4, 5]; let sample = [1, 3]; let output = isSubsetOf(base, sample); console.log(output); // --> true 해석(수도코드) 단순히 비교 분석만 한다면 굉장히 쉬운 문제이지만 '효율'을 생각해보았을 때에 조금 더 복잡 해지는 것 같습니다. sort 메서드를 사용하여 각 배열의 숫자를 정렬을 합니다. 그렇게 되면 비교하는 횟수를 줄일 수 있으며 좀 더 효율적으로 비교가 가능합니다. sample 요소 하나를..
Toy 문제2
문제 재귀함수를 사용하여 피보나치 수열 나타내기 반복문 사용 금지 해석(수도코드) 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 보통 첫 번째는 0, 두 번째는 1로 고정이 되어있고. n>=2 이라면 (n-1)(n-2) 공식이 성립되는 식입니다. 하지만 무작정 재귀 함수를 사용하여 피보나치수열을 나타내게 되면 // let fibonacci = function (n) { // if (n { if (result[n] !== undefined) return result[n]; result[n] = fibo(n - 1) + fibo(n - ..
Toy 문제 1
문제 숫자 N 숫자 N의 경우의 수를 나열하였을 때 K가 몇 번째 위치한 경우의 수 인지 찾아야 합니다. 모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다. ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 해석 (수도코드) N이 작은 값일 때에는 모든 경우의 수를 구하는 것을 펙토리얼로 구하는 것이 나쁘지 않을 수 있지만, 12!는 약 4억 8천만에 해당하며, 일반적인 수행 속도 상한(약 1억)을 훨씬 상회하므로 순열을 전부 생성하는 것은 올바른 접근 방법이 아닙니다. 그렇기 때문에 배열 번호가 작을수록 앞에 위치해야 한다는 점을 펙토리얼과 함께 활용 해야 합니다. 숫자 N을 5 K가 [3, 2, 1, 4, 5] 라..