10장. 검색과 정렬 검색 (search) - 검색은 자료 구조 내에 특정 항목을 찾는 일을 말하며, 배열이 정렬됐는지 여부에따라 두 가지 주요 기법이 있다. 선형 검색 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작한다. 시간 복잡도 : O(n) 배열의 정렬 여부와는 관계없이 동작하기때문에 좋으므로 정렬되지 않은 배열을 검색하기 좋다. function linearSearch(arr, n) { for(var i = 0; i < arr.length; i++){ if (arr[i] == n) return true; } return false; } 이진 검색 (탐색) 중간 값을 확인해서 원하는 값보다 중간 값이 작은지 큰지를 확인하면서 동작한다. 시간 복잡도: O(logn) 이진 탐색은 빠르지만 배열..
7장. 자바스크립트 메모리 관리 메모리 누수 자바스크립트는 타언어와는 달리 프로그래머가 직접 메모리를 수동으로 할당하고 해제하지 않고 사용하지않는 변수, 즉 메모리를 삭제해주는 가비지 컬렉터가 있기 때문에 매니지드언어라고 부른다. 하지만 이러한 기능에도 메모리가 올바른 방식으로 해제되지 않아 메모리 누수가 발생할 수 있기 때문에 이를 피하기위한 여러 방법이 존재한다. 객체에 대한 참조 var foo = { bar1: memory(), // 5kb bar2: memory(), // 5kb } function clickEvent() { alert(foo.bar1[0]); } 객체에 대한 참조가 있다면 해당 참조는 메모리에 존재하는 것이다. foo객체가 bar1만을 참조하더라도 foo객체 전체를 clickEv..
배세민, ⌜자바스크립트로하는 자료구조와 알고리즘⌟, 에이콘, 2019 - 요약 및 배운점 정리 1장. 빅 오 표기법 빅오 표기법이란? 빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정하는 방법이다. 빅오 표기법에서 n은 입력의 개수를 나타내며, 알고리즘 구현시 해당 알고리즘이 얼마나 효율적인지를 나타낼 수 있는 방법이기에 중요하다! 빅오 표기법은 O()로 나타낼 수 있는데 O(1)은 상수시간, 즉 입력 공간에 대해 변하지 않음을 나타내고 O(n)은 선형시간으로 최악의 경우에 n번의 연산을 수행해야하는 알고리즘이 이에 해당한다. 빅오 표기법의 규칙 알고리즘의 시간 복잡도를 f(n)이라 표현한다. f(n)을 계산함으로써 알고리즘의 효율성을 이해할 수 있지만 계산이 어려울 수 있기 때문에 이에 도움이 되는 ..
cs지식/자료구조 2022. 7. 13. 16:40
10장. 검색과 정렬 검색 (search) - 검색은 자료 구조 내에 특정 항목을 찾는 일을 말하며, 배열이 정렬됐는지 여부에따라 두 가지 주요 기법이 있다. 선형 검색 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작한다. 시간 복잡도 : O(n) 배열의 정렬 여부와는 관계없이 동작하기때문에 좋으므로 정렬되지 않은 배열을 검색하기 좋다. function linearSearch(arr, n) { for(var i = 0; i < arr.length; i++){ if (arr[i] == n) return true; } return false; } 이진 검색 (탐색) 중간 값을 확인해서 원하는 값보다 중간 값이 작은지 큰지를 확인하면서 동작한다. 시간 복잡도: O(logn) 이진 탐색은 빠르지만 배열..
cs지식/자료구조 2022. 7. 3. 22:57
7장. 자바스크립트 메모리 관리 메모리 누수 자바스크립트는 타언어와는 달리 프로그래머가 직접 메모리를 수동으로 할당하고 해제하지 않고 사용하지않는 변수, 즉 메모리를 삭제해주는 가비지 컬렉터가 있기 때문에 매니지드언어라고 부른다. 하지만 이러한 기능에도 메모리가 올바른 방식으로 해제되지 않아 메모리 누수가 발생할 수 있기 때문에 이를 피하기위한 여러 방법이 존재한다. 객체에 대한 참조 var foo = { bar1: memory(), // 5kb bar2: memory(), // 5kb } function clickEvent() { alert(foo.bar1[0]); } 객체에 대한 참조가 있다면 해당 참조는 메모리에 존재하는 것이다. foo객체가 bar1만을 참조하더라도 foo객체 전체를 clickEv..
cs지식/자료구조 2022. 6. 30. 16:14
5장. 자바스크립트 배열 배열 삽입 새로운 항목을 자료 구조 내에 추가하는것. .push(element)메소드를 사용해 배열 삽입을 구현할 수 있다. var arr = [1, 2, 3, 4] arr.push(5); // arr = [1, 2, 3, 4, 5] arr.push(8); // arr = [1, 2, 3, 4, 5, 8] // 시간복잡도: O(1) 삭제 .pop()메소드를 사용해 배열 삭제를 구현할 수 있다. 해당 메소드는 제거된 항목을 반환한다. var arr = [1, 2, 3, 4] arr.pop(); // return 4, arr = [1, 2, 3] // 시간복잡도: O(1) arr.shift(); // return 1, arr = [2, 3] // shift()는 첫번째 항목을 제거한..
cs지식/자료구조 2022. 6. 29. 16:30
배세민, ⌜자바스크립트로하는 자료구조와 알고리즘⌟, 에이콘, 2019 - 요약 및 배운점 정리 1장. 빅 오 표기법 빅오 표기법이란? 빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정하는 방법이다. 빅오 표기법에서 n은 입력의 개수를 나타내며, 알고리즘 구현시 해당 알고리즘이 얼마나 효율적인지를 나타낼 수 있는 방법이기에 중요하다! 빅오 표기법은 O()로 나타낼 수 있는데 O(1)은 상수시간, 즉 입력 공간에 대해 변하지 않음을 나타내고 O(n)은 선형시간으로 최악의 경우에 n번의 연산을 수행해야하는 알고리즘이 이에 해당한다. 빅오 표기법의 규칙 알고리즘의 시간 복잡도를 f(n)이라 표현한다. f(n)을 계산함으로써 알고리즘의 효율성을 이해할 수 있지만 계산이 어려울 수 있기 때문에 이에 도움이 되는 ..