알고리즘 (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

알고리즘 (JS)

알고리즘 개념

알고리즘이란? 어떤 문제를 해결하기 위해서 잘 정리된 방법! 예를 들어, 요리를 하기 위해서 필요한 레시피를 알고리즘이라고 생각하면 된다. 컴퓨터 프로그래밍으로 예를 들면, 두 개의 숫자를 더하는 알고리즘에 a, b라는 숫자를 넣고 알고리즘을 통해서 계산한 값을 출력한다. 여기서 알고리즘은 1. '+' 기호를 통해 두 개의 숫자를 더한다. 2. 그 값을 출력한다. 알고리즘은 input, output이 정확해야 하고, 그 단계가 명확해야 한다. 왜 사용해야 할까? 알고리즘은 다양한 방법이 있을 수 있고 그 중 가장 효율적인 방법을 통해서 문제를 해결해야 한다. 그러면 많은 방법 중 어떤 방법이 가장 효율적인지는 어떻게 계산하면 될까? 알고리즘 비교하기 알고리즘이 실행되는 시간을 정확하게 측정하는 것은 어렵..

2023. 11. 21. 15:08