본문 바로가기

✘✘✘ Algorithm + Data structure9

Prime Number:: 소수 찾기 코드 javascript 1. 기본 접근 방식(Brute Force): 소수를 찾는 순진한 접근 방식은 2에서 대상 숫자까지 모든 숫자를 반복하고 각 숫자에 대해 1과 자기 자신 이외의 숫자로 나눌 수 있는지 확인하는 것입니다. 나눌 수 없으면 그 숫자는 소수입니다. 다음은 JavaScript의 예입니다. javascriptCopy code function isPrime(number) { if (number 2023. 4. 9.
[sort] Quick sort, 퀵 소트- 1 pivot function quickSort(arr) { quickSortRecursivley(arr, 0, arr.length - 1); return arr; } function quickSortRecursivley(arr, s, e) { if (s >= e) return; const pivotIndex = partition(arr, s, e); quickSortRecursivley(arr, pivotIndex + 1, e); quickSortRecursivley(arr, s, pivotIndex - 1); } function partition(arr, s, e) { let pivot = e; let left = s; let right = e; let pointer = left; let pivotNumber = .. 2023. 4. 5.
p, np, np-complete, np-hard + polynomial time(n^k: n is the size of input, k is constant) from lecture 결정론적 튜링 기계 p: 결정론적 튜링 기계로 다항식 시간 안에 풀 수 있는 문제 np: 비결정론적 튜링 기계로 풀 수 있는 문제 중 > 정답이 있을 때 결정론적 튜링 기계로 다항식 시간 안에 검증 가능한 문제 np-complete: intersection of np ∩ np-hard. np-hard: np가 아닌데 np가 붙어 있다 =_= | p ⊂ np | np-complete = np ∩ np-hard | np-complete ⊂ np from ChatGPT P, NP 및 NP-완전 다이어그램은 계산 복잡도 이론에서 결정 문제의 복잡도 클래스를 나타냅니다. 각 클래스와 그 관계에 대한 간략한 설명은 다음과 같습니다. P: 클래스 P는 결정론적 알고리즘에 의해 다항 시간 내에 .. 2023. 3. 25.
DFS: 깊이 우선 탐색- iteration, recursion Chapter 7 DFS DFS - Depth first search function dfsRecursion(adjacencyList: Array, here: number, visited: boolean[]) { visited[here] = true; const currentEdges = adjacencyList[here]; for (let i = 0; i < currentEdges.length; i++) { const connectedVertex = currentEdges[i]; if (visited[connectedVertex] === true) continue; dfsRecursion(adjacencyList, connectedVertex, visited); } } function dfsIterat.. 2023. 1. 15.
[Quick Sort] Quick Select Quck sort, Quick Select Quick Sort function quickSortWidthEndPivot(arr, start, end) { if (start >= end) { return arr; } let left = start; let right = end - 1; let pivot = end; while (left arr[pivot] && high < arr[pivot]) { swap(arr, left, right); } if (low = arr[pivot]) right--; } swap(arr, left, pivot); pivot = left; // renew pivot position for next process quickSortWidthEndPivot(arr, start, pi.. 2023. 1. 7.
[Counting sort] 계수정렬 Counting sort const MAX_NUM = 10000; const MAX_SIZE = 10000; function countingSort(numbers) { let maxNum = -Infinity; for (const n of numbers) { if (n 2023. 1. 1.
[subset] find all subsets Number of Subsets of a given Set: If a set contains ‘n’ elements, then the number of subsets of the set is 2n. Number of Proper Subsets of the Set: If a set contains ‘n’ elements, then the number of proper subsets of the set is 2n - 1. | If A = {p, q} the proper subsets of A are [{ }, {p}, {q} with loop const nums = [1, 2, 3]; const subsets = [[]]; function findSubsets(subsets, nums, currentSet,.. 2022. 12. 25.
[BST] Construct binary search tree methods :: insert, contains, remove(delete) BST definition BST class BST { constructor(value) { this.value = value; this.left = null; this.right = null; } insert(value) { let currentNode = this; while (currentNode !== null) { if (currentNode.value > value) { if (currentNode.left === null) { currentNode.left = new BST(value); } else { currentNode.left.insert(value); } } else { if (currentNode.right === null) { currentNode.right = new BST(v.. 2022. 7. 4.
시작: 어차피 한 번은 끝장을 봐야 한다 목표 알고리즘 문제를 보고 필요한 자료 구조, 알고리즘, 문제 해결 전략을 떠올리고 코딩할 수 있다. 목적 글로벌 IT 기업 코딩 테스트, 인터뷰 알고리즘을 흥미를 가지고 이어갈 수 있는 기초 함양 생각을 코드로 표현할 수 있는 능력 향상 종만북, 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 백준 Ranker에게 과외 Corsera Algorithm part 1, Princeton University AlgoExpert 160 Coding Interview Questions 2022. 7. 2.

티스토리툴바