본문 바로가기

Bootcamp/Algorithm40

[algorithm] 수도쿠 Sudoku 풀이 알고리즘 문제: 2차원 배열 형태의 수도쿠 문제를 입력 받아 풀이를 리턴하는 함수 작성. 0인 위치는 채워야할 빈칸이다. 예시: 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); // -.. 2021. 11. 24.
[algorithm] PowerSet 부분집합 구하기 문제 하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 합니다. 입력: string 타입의 공백이 없는 알파벳 소문자 문자열 출력: 배열(arr)을 리턴해야 합니다. arr[i]는 각 부분집합의 원소로 구성된 문자열 주의: 1. 부분집합은 빈 문자열을 포함합니다. 2. arr은 사전식 순서(lexical order)로 정렬되어야 합니다. 3. 집합은 중복된 원소를 허용하지 않습니다. 4. arr[i]는 알파벳 순서로 정렬되어야 합니다. 예시: let output2 = powerSet('jjump'); console.log(output2); // ['', 'j', 'jm', 'jmp', .. 2021. 11. 23.
[Data Structure] JavaScript로 이진탐색트리(BST) 자료형 만들기 API new BinarySearchTree (value); bst. insert (value); bst. contains (value); bst. preorder (callback); bst. inorder (callback); bst. postorder (callback); class BinarySearchTree { constructor(value) { this.value = value; this.left = null; this.right = null; } insert(value) { if (value < this.value) { if (this.left === null) { this.left = new BinarySearchTree(value); } else { this.left.insert(va.. 2021. 11. 14.
[algorithm] 부분집합의 수 구하기 문제 tree의 모든 edge를 담은 2차원 배열이 주어졌을 때 독립된(서로 떨어져있는) 서브트리의 개수 구하라 예를 들어 [[0, 1], [2, 3], [3, 4], [4, 5]] 와 같이 주어진 트리에는 (0-1), (2-3-4-5) 두 개의 독립된 서브트리가 있다. 코드 function numberOfSubTrees(tree) { let count = 0; const len = tree.length; // 코드에서 자주 쓸 거라서 따로 변수로 만든다. let visited = new Array(len).fill(false); // edge 방문 여부를 담을 배열을 만들고 초기값은 false로 설정 for (let i = 0; i < len; i++) { // 모든 edge를 돌면서 let queue.. 2021. 11. 13.
[algorithm] Fibonacci 수열 알고리즘 - 개선된 알고리즘 문제: 재귀함수를 이용하여 피보나치 수열을 만드는 알고리즘을 개선하기 기존 알고리즘 // 효율이 떨어지는, 재귀로 구현하는 피보나치수열 function fibonacci(n) { if (n === 0) return 0; if (n === 1) return 1; return fibonacci(n - 1) + fibonacci(n - 2); } /* 알고리즘의 문제점 fibonacci수열을 반복해서 계산하는 문제가 있다. 예를 fibonacci(5)를 구할 때, fibonacci(5) = fibonacci(4) + fibonacci(3) = (fibonacci(2) + fibonacci(3)) + (fibonacci(1) + fibonacci(2)) = (fibanacci(0) + fibonacci(1) +.. 2021. 11. 11.
[algorithm] 백준 2178 - 미로탐색 [문제] 백준 2178 - 미로탐색 [링크] https://www.acmicpc.net/problem/2178 [기본] BFS 탐색 [푸는데 걸린 시간] 약 3시간 let input = require('fs').readFileSync('testcase_04.txt').toString().split('\n'); const [n, m] = input[0].split(' '); const maze = []; const mark = []; for (let i = 0; i < n; i++) { maze[i] = []; mark[i] = []; const tmp = input[i + 1].split(''); for (let j = 0; j < m; j++) { maze[i][j] = +tmp[j]; mark[i][.. 2021. 11. 5.
[algorithm] 백준 1926 - 그림, BFS [문제] 백준 알고리즘 1926, 그림 [링크] https://www.acmicpc.net/problem/1926 푸는데 걸린 시간: 약 5시간 let input = require('fs').readFileSync('/dev/stdin').toString().split('\n'); const [n, m] = input[0].split(' '); const picture = []; for (let i = 0; i { let count = 0; let biggestArea = 0; c.. 2021. 11. 1.
[algorithm] 백준 1963 - 소수경로 [문제] https://www.acmicpc.net/problem/1963 let input = require(&#39;fs&#39;).readFileSync(&#39;testcase.txt&#39;).toString().split(&#39;\n&#39;); const eratos = new Array(9999).fill(true); for (let i = 2; i * i { const queue = []; const visited = []; visited[a] = 0; queue.push(a); while(queue.lengt.. 2021. 10. 31.

티스토리툴바