JavaScript/Basic
-
[JS 알고리즘&자료구조] Big O 표현식의 단순화JavaScript/Basic 2023. 10. 26. 00:40
5n + 2라는 식이 있다고 하자. 여기서 연산이 몇개가 더 추가된다고 하더라도 결국 n의 값과 비례하여 실행 시간이 증가하는 추세를 보이기 때문에 Big O 표기법을 적용하면 O(n)으로 표기가 된다. 이 장에서는 Big O 표기법을 단순화하는 몇 가지 방법들에 대해서 살펴보려고 한다. (강사의 경험을 기반으로 하고 있다.) 중요한 것은 큰 그림이라는 점을 기억하자. 1. 상수는 신경쓰지 않아도 된다. O(2n)이 있다면 그냥 O(n)으로 표기하면 되며 O(500)이 있다면 O(1)로 표시해주면 된다. O(13n²) 또한 상수인 13은 무시한 채로 O(n²)로 표기해준다. 이렇게 표기하게 되면 O(1)이 O(n)보다는 빠르고 O(n)이 O(n²)보다는 빠르다는 사실을 이미 알고 있기 때문에 비교하기가 ..
-
[JS 알고리즘&자료구조] Big O에 대한 공식 소개JavaScript/Basic 2023. 10. 26. 00:05
드디어 빅오의 추상적인 개념이 아닌 정확히 빅오가 무엇인지 살펴보자. 1. 숫자를 세는 것을 공식화한 것 2. 입력 값이 늘어날수록 알고리즘의 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식 (입력 값과 실행 시간의 상관 관계를 표시) 앞 장에서 우리는 addUpToFirst는 입력 값 n에 따라 실행 시간이 선형적으로 계속 증가하는 것을 볼 수 있었고 addUpToSecond 함수는 입력 값 n과는 무관하게 실행 시간이 거의 0에 수렴하는 것을 볼 수 있었다. 이렇게 입력값과 실행 시간 간의 상관 관계를 시각화 하는 것을 Big O라고 할 수 있다. Big O의 결과는 크게 4가지로 볼 수 있다. 1. O(n) : 실행 시간이 입력 값과 선형적 비례를 이룬다. (예시 : addUpToFirst) 예..
-
[JS 알고리즘&자료구조] 시간 복잡도 시각화하기JavaScript/Basic 2023. 10. 25. 00:25
걸리는 시간도 연산의 갯수보다도 큰 그림을 보는 것이 중요하다고 앞에서 얘기했으니 이제 큰 그림을 보는 시간을 가져보려고 한다. 아래의 홈페이지에 들어가면 앞에서 예시로 들었던 addUpToFirst와 addUpToSecond 함수를 실행시키고 해당 코드들이 결과값을 뱉기까지 얼마나 시간이 걸리는지 추세를 나타내준다. 우선 addUpToFirst 함수의 추세선을 살펴보자. 입력되는 n의 값에 따라 시간이 기하급수적으로 느는 것을 확인할 수 있다. 앞의 장에서 봤듯이 해당 로직은 n의 숫자만큼 연산의 갯수가 늘어나기 때문에 당연히 시간도 늘어나는 것을 알 수 있다. 다음으로 addUpToSecond 함수의 추세선을 보자. n의 값으로 어떤 것이 입력되도 해당 함수는 3개의 연산만을 실행하기 때문에 시간이 ..
-
[JS 알고리즘&자료구조] 연산 갯수 새기JavaScript/Basic 2023. 10. 25. 00:10
앞에서 봤듯이 코드를 비교할 때 시간을 기준으로 하는 것은 문제가 된다는 걸 알게 되었다. 그렇다면 시간 말고 컴퓨터가 결과를 출력해내기 위해 실행해야만 하는 연산의 갯수를 세는 것은 어떨까? 아래 코드를 보자. const addUpTo = (n) => { return n * (n+1) / 2; // 곱하기 1회, 더하기 1회, 나누기 1회 } 위의 코드에서는 총 3회의 연산이 진행된다는 것을 알 수 있다. 아래의 다른 코드를 보자. const addUpTo = (n) => { let total = 0; for (let i = 1; i
-
[JS 알고리즘&자료구조] 코드 시간 재기JavaScript/Basic 2023. 10. 24. 00:18
N이라는 숫자가 주어지면 1부터 N까지의 합을 구해주는 함수를 짠다고 해보자. 일반적으로는 아래와 같이 짤 수 있다. const addUpTo = (n) => { let total = 0; for (let i = 1; i { return n * (n+1) / 2; } console.log(addUpTo(6)); 둘 중 어떤 것이 더 나은 코드라고 할 수 있을까? (아무것도 모르는 상태에서는 난 2번을 고르겠다 🙄) 애초에 '더 좋은' 코드라는 건 어떤 걸 뜻하는 걸까? 결과 값이 더 빨리 나오는 코드? 아니면 메모리를 더 적게 사용하는 코드? 가독성이 더 높은 코드? 상황에 따라 다르지만 대개 사람들은 결과 값이 더 빨리 나오거나 메모리를 더 적게 사용하는 코드를 '더 좋은' 코드라고 정의힌다. 당연히 ..
-
[JS 알고리즘&자료구조] Big O 표기법 소개JavaScript/Basic 2023. 10. 23. 23:51
1. Big O 표기법의 필요성 어떤 주제에 대해서 수십개의 해결법이 존재한다. 매개변수와 이름이 다른 수준을 떠나 아예 접근 방식 자체가 다르다. 어떤 것이 가장 좋은 방법인지 알아내는 방법이 존재할까? 이것이 Big O의 핵심이다. Big O는 여러가지 코드를 서로 비교하고 성능을 표기하는 시스템이다. 2. Big O 표기법이란? 위에서 말했듯이 Big O는 여러가지 코드를 서로 비교하고 성능을 표기하는 시스템이다. Big O 표기법을 통해 우리는 숫자로 코드의 성능을 표기할 수 있다. 3. 코드의 성능이 그렇게 중요한가? 누군가는 코드의 성능보다는 제대로 작동하는 게 더 중요하다고 말할 수도 있다. 사실 때에 따라서는 제대로 작동하는 게 가장 중요하기도 하다. 하지만 면접을 보거나, 코딩 테스트를 ..