TIL- 22.02.17 목

자바스크립트- 스코프

참조 대상 식별자(변수, 함수, 클래스의 이름)를 찾는 규칙.

선언한 변수의 접근(참조)할 수 있는 범위를 말한다.

크게 global scope와 local scope 로 나눌 수 있으며, local scope에 block level scope와 function level scope가 속한다.

전역 변수는 global scope이고, 함수 외부에서 선언된 변수를 말한다. 어디에서든 접근이 가능하다.

지역 변수는 local scope 이고, 함수 내에서 선언된 변수를 말한다. 함수 내에서만 사용 가능하며 함수 외부에서는 접근이 불가능하다.

자바스크립트는 일반적인 c언어 계열 언어들이 블록 레벨 스코프를 따르는 것과 다르게 함수 레벨 스코프를 따른다.

var 키워드는 함수 레벨 스코프를 따르기 때문에 블록(브라켓, if, for, while, try/ catch) 내에서 선언되어도 전역 변수가 된다. 함수 내에서 선언될 경우에만 지역 변수가 된다.

es6에서 블록 레벨 스코프로 let, const 키워드가 추가되었다.

 

 

 

이진 탐색 (Binary Search)

정렬된 배열에서 좌, 우 두개의 포인터 사이 가운데를 선택해서 범위를 빠르게 줄여나가는 알고리즘이다. 배열이 정렬되어 있을 경우에만 사용 가능하다.

단순 탐색 방식은 배열의 모든 요소를 하나씩 찾기 때문에 굉장히 시간이 오래 걸리지만 이진 탐색으로 찾을 경우 단순 탐색으로 찾을 때 보다 시간을 빠르게 단축할 수 있다.

원소의 개수가 커질수록 단순 탐색과 이진 탐색의 실행 시간의 차이는 기하급수적으로 차이가 난다. (시간복잡도)

예를 들어 100가지 숫자 중 하나의 수를 찾으려면 단순 탐색의 경우 최악의 경우 100번이나 찾아야 하지만 이진 탐색으로 찾을 경우 최악의 경우여도 7번만에 찾을 수 있고,

24만개의 단어 중 하나의 단어를 찾는 경우 단순 탐색방식으로는 최대 24만번 찾아야 하지만 이진 탐색으로는 최대 18번만에 찾을 수 있다.(24만을 2로 1이 될 때까지 나눈 횟수)

 

빅 오 표기법

알고리즘이 동작하기 위해 필요한 연산 횟수를 나타내는 표기법이다. 알고리즘이 얼마나 빠른지를 말해준다.

실행 시간이 빠른 순서대로 나열

1. O(log n), 로그 시간 - 이진 탐색
2. O(n), 선형 시간 - 단순 탐색
3. O(n * log n) - 퀵 정렬
4. O(n2) - 선택 정렬
5. O(n!) - 외판원 문제