알고리즘 (JS)

The Other Algorithms

Cartesian product 두 개의 set에서 각 요소의 곱을 나타내는 방법이다. 예를 들어, A = [1, 2] / B = [3, 4] 가 있다면 AxB = [[1, 3], [1, 4], [2, 3], [2, 4]] 이런 식으로 나타내게 된다. function cartesian(arr1, arr2) { const result = []; for (let i = 0; i < arr1.length; i++) { for (let j = 0; j < arr2.length; j++) { result.push([arr1[i], arr2[j]]) } } return result } 이렇게 되면 Big O는 O(mn)가 된다. arr1과 arr2의 길이가 다르기 때문에 그걸 곱한 게 새로운 배열의 길이가 되고 O..

2023. 11. 22. 17:31

알고리즘 (JS)

Sorting Algorithms

Bubble Sort 실제로는 많이 쓰이지 않지만 기본적으로 알고 있어야 하는 방법이다. 근접한 요소끼리 비교해서 내가 원하는 순서대로 정렬하는 것을 반복하고 만약 요소들이 순서가 변경되지 않았다면 제대로 정렬이 된거니까 완료한다. function bubbleSort(arr) { let swapped = do { swapped = false for(let i = 0; i arr[i+1]) { let temp = arr[i] arr[i] = arr[i+1] arr[i+1] = temp swapped = true } } } while(swapped) } Big O : O(n^2) Insertion Sort 정렬이 된 배열과 정렬이 되지 않은 배열이..

2023. 11. 22. 16:40

알고리즘 (JS)

Search Algorithms

Linear Search 주어진 배열에서 어떤 특정 요소를 찾아서 배열의 인덱스를 리턴해라, 만약 값이 없다면 -1을 리턴해라 function func(arr, num) { for (let i = 0; i idx === num) } * 여기서 forEach를 사용해서 중간에 인덱스를 찾아 return을 하게 되더라도 그 콜백함수의 반환값이 func 함수의 반환값이 되지 않기 때문에 마지막 리턴값을 내보내게 된다 --> 따라서 올바른 인덱스가 아니라 모든 경우에 -1을 반환한다. 그래서 사용..

2023. 11. 21. 23:05

알고리즘 (JS)

Math Algorithms

Fibonacci Sequence 앞의 두 개의 정수를 더한 값이 오는 배열 예를 들어, fibonacci(7) = [0, 1, 1, 2, 3, 5, 8] 가장 첫 값은 [0, 1] 로 시작한다. function fibonacci(n) { const fib = [0, 1]; for (let i = 2; i for문이 있기 때문에 입력받은 n의 영향을 받게 됨 Factorial of a number 입력 받은 숫자보다 작거나 같은 정수를 모두 곱한 것. 0의 팩토리얼은 1 function factorial(n) { let ret = 1 for (let i = 2; i for문이 ..

2023. 11. 21. 22:07

알고리즘 (JS)

Big-O로 보는 자바스크립트의 Object와 Array

왜 알아야 할까 우리가 너무 익숙하게 사용하는 객체와 배열의 메서드를 사용할 때마다 어떤 복잡도를 갖는지를 알아야 계산이 가능하기 때문이다. for문 안에서 만약 배열을 slice 하거나 index를 찾기위해 indexOf 와 같은 메서드를 사용하는 경우 순식간에 복잡도는 O(n^2) 가 되어버리기 때문에 ,, 항상 하나를 사용하더라도 주의해서 사용해야 한다. Object 키와 값으로 이루어진 자바스크립트의 객체 const person = { firstName: 'yy'; lastName: 'k'; } insert : O(1) remove : O(1) access : O(1) search : O(n) -> 최악의 경우에는 모든 요소를 다 돌아야 찾을 수 있기 때문! Object.keys() : O(n) ..

2023. 11. 21. 15:43

알고리즘 (JS)

Big-O Notation

Big-O Notation 알고리즘의 복잡도를 나타내기 위한 worst case 복잡도이다. - 입력값에 대해서 표현된다. - 작은 디테일보다는 큰 그림에 대해 집중하는 방법이다. Time Complexity Linear Complexity : O(n) function summation(n) { let sum = 0; for (let i = 1; i < = n; i++) { sum += i; } return sum; } 위의 소스코드 예시에서 실행되는 구문은 2, 4, 6번 라인에 있는 부분이다. 만약 n이 4라는 숫자가 들어갔다면, 2번 라인은 1번 / 4번 라인은 4번 / 6번 라인은 1번 해서 총 6번 즉, n + 2 라는 식이 나오게 된다. (입력값에 따라서 달라지게 된다는 첫번째 특성) 그리고 ..

2023. 11. 21. 15:32