자바스크립트로 하는 자료구조와 알고리즘 - 1~4장

pIutos 2022. 7. 15. 14:46

배세민, ⌜자바스크립트로 하는 자료구조와 알고리즘⌟, 에이콘, 2019
- 요약 및 배운점 정리

1장. 빅 오 표기법

빅오 표기법이란?

빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정하는 방법이다. 빅오 표기법에서 n은 입력의 개수를 나타내며, 알고리즘 구현시 해당 알고리즘이 얼마나 효율적인지를 나타낼 수 있는 방법이기에 중요하다!

빅오 표기법은 O()로 나타낼 수 있는데 O(1)은 상수시간, 즉 입력 공간에 대해 변하지 않음을 나타내고 O(n)은 선형시간으로 최악의 경우에 n번의 연산을 수행해야하는 알고리즘이 이에 해당한다.

빅오 표기법의 규칙

알고리즘의 시간 복잡도를 f(n)이라 표현한다. f(n)을 계산함으로써 알고리즘의 효율성을 이해할 수 있지만 계산이 어려울 수 있기 때문에 이에 도움이 되는 기본적인 여러가지 규칙이 존재한다.

계수 법칙 - "상수를 제거하라"

상수 k > 0인 경우 f(n)이 O(g(n))이면 kf(n)은 O(g(n))이다.

n과 관련되지 않은 계수는 제거하는 규칙으로, 5f(n)과 f(n)은 모두 동일한 O(f(n))이다.

-> f(n) = 5n, f(n) = n + 1인 경우는 모두 O(n)의 빅오표기법이다.

합의 법칙 - "빅오를 더하라"

코드에서 f(n)=n과 f(n)=4n이 각각 실행된다면 합의 법칙에 의해 f(n) = 5n이다. 이때 계수법칙에 의해 최종적 결과는 O(n)=n이다.

곱의 법칙 - "빅오를 곱하라"

코드에서 루프에 의해 5n번 실행되고 내부 루프가 외부 루프에의해 n번 실행된다면 f(n) = 5n x n이다. 이때 계수법칙에 의해 O(n) = n^이다.

다항 법칙 - "빅오의 k승"

f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.

...
for (var i=0; i<n*n; i++) {
	conut+=1;
}
// count+=1;이 n*n번 실행되기 떄문에 f(n)=n^2이다.

2장. 자바스크립트의 독특한 특징

자바스크립트 범위

범위(scope)는 자바스크립트 변수에 대한 접근 권한을 정의하는 것이다. 자바스크립트에서 변수는 전역 범위 또는 지역 범위에 속할 수 있다.

전역 범위 - 연산자 없이 변수를 선언하게되면 전역변수를 생성함
함수 범위 - var

- 변수 호이스팅 (variable hoisting) : var를 사용하여 변수를 선언하면 어디에서 선언하든 변수 선언이 함수의 맨 앞으로 이동한다.

function scope(print){
	if(print){
    	var insideIf = '12';
    }
    console.log(insideIf);
}
scope(true) // 12출력, 오류발생x

function scope(print){
	var insideIf
    
	if(print){
    	insideIf = '12';
    }
    console.log(insideIf);
}
scope(true)
//위의 함수와 동일하다. var은 함수범위로 정의되며 호이스팅이 일어난다.

블록 범위 - let, const : 변수가 선언된 { } 내에서만 유효함

function scope(print){
	if(print){
    	let insideIf = '12';
    }
    console.log(insideIf);
}
scope(true) // 12 x, ''를 출력함

등가와 형

변수형

boolean, number, string, undefined, object, function, symbol

-> 선언만 되고 값이 할당되지 않은 변수에는 undefined가 할당된다.

true / false 확인

if 내의 매개변수는 대개의 다른 언어와는 달리 꼭 boolean형이 아니어도 된다.

- false로 평가되는 경우 : false, 0, '', "", NaN, undefined, null

- true로 평가되는 경우 : true, 0이 아닌 다른 숫자, 비어있지 않은 문자열, 비어있지 않은 객체

=== vs ==

자바스크립트는 변수 선언 시 변수에 형이 할당되지 않으며, 코드가 실행될 때 해당 변수의 형이 해석된다. 따라서 ===는 ==에 비해 등가를 조금 더 엄격히 확인한다.

==: 값만 같은지 여부를 확인

===: 형과 값 모두 같은지 여부를 확인

객체

var object1 = {};
var object2 = {};

console.log(object1 == object2); //false
console.log(object1 === object2); //false

- 동일한 속성과 값을 가져도 두 변수의 메모리상 주소는 다르기 때문에 두 객체는 동일하지 않다.

var function1 = function(){console.log(2)};
var function2 = function(){console.log(2)};

console.log(function1 == function2); //false

- 동일한 연산을 수행해도 두 함수의 메모리상 주소는 다르기 때문에 두 함수는 동일하지 않다.

→ ==, ===연산자는 숫자, 문자열, 불리언과 같은 비객체형에만 사용가능하다! (객체와 함수에서는 사용x)

3장. 자바스크립트 숫자

숫자 체계

자바스크립트는 숫자에 대해 64비트 부동소수점 표현을 사용한다. 63번째 비트는 부호를, 63~52번째 비트는 지수 값 e를, 나머지 52비트는 분수 값을 나타낸다. 이 64비트값은 어려운 공식에 의해 계산되는데, 이러한 십진분수로 인하여 자바스크립트에서 부동소수점 체계가 반올림 오류를 일으킬 수 있다. 이러한 이유 때문에 0.1과 0.2는 정확히 표현할 수 없다. 따라서 0.1 + 0.2 === 0.3의 결과는 false이다.

자바스크립트 숫자 객체

위와같은 숫자 체계의 문제를 해결하는데 도움이 되는 Number객체의 내장된 속성이 있다

정수 반올림

자바스크립트는 정수를 정수형으로 명시적으로 선언하지 않고 모든 숫자를 표현할 때 부동소수점을 사용하기 때문에 정수 나눗셈을 하면 부동소숫점의 결과가 나온다. (5/4 = 1.25) 따라서 정수 나눗셈을 하기위해서는 아래와 같은 함수를 이용해야한다.

Math.floor()
Math.round()
Math.ceil()

Number.EPSILON

두 개의 표현 가능한 숫자 사이의 가장 작은 간격을 반환한다.

function numberEquals(x, y) {
	return Math.abs(x - y) < Number.EPSILON;
}
numberEquals(0.1 + 0.2, 0.3) // true

최대치

Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2; // true

Number.MAX_VALUE + 1 === Number.VALUE + 2; // true

Number.MAX_SAFE_INTEGER: 가장 큰 정수를 반환

Number.VALUE: 가장 큰 부동소수점 수를 반환

최소치

Number.MIN_SAFE_INTEGER - 1 === Number.MIN_SAFE_INTEGER -2; // true

Number.MIN_VALUE -1 == -1; // true

Number.MIN_SAFE_INTEGER: 가장 작은 정수를 반환

Number.MIN_VALUE: 가능한 가장 작은 부동소수점 수를 반환 -> 음수가 아님! (Number.MIN_SAFE_INTEGER < Number.MIN_VALUE)

무한

Infinity > Number.MAX_SAFE_INTEGER; // true
-Infinity < -Number.MAX_SAFE_INTEGER; // true
-Infinity - 32323323 == -Infinity - 1; //true: -Infinity보다 작아질 수 있는것은 없음

크기 순서

-Infinity < Number.MIN_SAFE_INTEGER < Number.MIN_VALUE < 0 < Number.MAX_SAFE_INTEGER < Number.MAX_VALUE < Infinity

무작위 수 생성기

자바스크립트에는 숫자를 생성하기 위핸 내장 함수인 Math.random()이 있다. 이 함수는 0과 1 사이의 무작위 부동 소수점을 반환한다.

4장. 자바스크립트 문자열

자바스크립트 문자열 기본

문자열 접근

문자에 접근하기 위해 .charAt(index)을 사용할 수 있다.

'dog'.charAt(1); // "o"

문자열 접근을 위해 .subString(startIndex, endIndex)을 사용할 수 있다. subString은 지정된 인덱스 사이의 문자들을 반환한다. endIndex를 전달하지 않으면 지정된 시작위치부터 끝까지 모든 문자를 반환한다.

'YouTube'.substring(1,2) // 'o'
'YouTube'.substring(3,6) // 'Tub'
'YouTube'.substring(2) // 'uTube'

문자열 비교

자바스크립트에서는 < 와 >를 이용하여 쉽게 문자열을 비교할 수 있다.

console.log('a' < 'b') // true
console.log('abb' < 'b') // true
console.log('add' < 'ab') // false

문자열 검색

문자열 내에 특정 문자열을 찾기위해 .indexOf(searchValue[, fromIndex])를 사용할 수 있다. 일치하는 문자열을 찾으면 위치를 반환하고, 찾지 못한다면 -1을 반환한다.

'Red Dragon'.indexOf('Red') // 0
'Red Dragon'.indexOf('Dragon') // 4
'Red Dragon'.indexOf('Blue') // -1
'Red Dragon'.indexOf('Dragon', 2) // 4
'Red Dragon'.indexOf('Dragon', 6) // -1
'Red Dragon'.indexOf('', 9) // 9

startWith는 문자열이 특정 입력으로 시작하면 true를 반환하고, endsWith는 끝나면 true를 반환한다.

'Red Dragon'.startsWith('Dragon') //false
'Red Dragon'.endsWith('Dragon') //true

문자열 분해

문자열을 여러 부분으로 나누기 위해 .split(separator)를 사용할 수 있다. separator를 입력받으면 부분 문자열 배열(Arr)를 생성한다.

'chicken,cow,pig'.split(","); // ["chicken", "cow", "pig"]
'chicken'.split(""); // ["c", "h", "i", "c", "k", "e", "n"]

문자열 바꾸기

.replace(string, replaceString) 문자열 변수 내에 특정 문자열을 다른 문자열로 대체할 수 있다.

"Red Dragon".replace("Red", "Blue"); // "Blue Dragon"

저작자표시 비영리 변경금지

'개발 도서 정리/자바스크립트로 하는 자료구조와 알고리즘'의 다른 글

more >

개발 창고