주벨로퍼의 개발 공부

1. 재귀

  1 - 1) 재귀 함수란 자기 자신을 호출하는 함수다.

  1 - 2) 재귀 함수는 '분할 정복' 방식을 통해 복잡한 문제를 해결한다.

2. 재귀의 규칙

  재귀 함수를 잘못 구현한 경우 심각한 문제를 일으킨다. 프로그램이 어느 한 곳에 빠져서 종료되지 않기 때문이다.

  무한 재귀 호출은 스택 오버플로(Stack Overflow)를 초래한다. 스택 오버플로란 프로그램의 콜 스택 최대 개수가

  제한된 양의 주소 공간(메모리)을 초과할 때를 나타낸다.

  2 - 1) 기저 조건

  재귀에는 기저 조건(종료 조건)이 존재한다. 아니 존재해야 한다! 재귀의 메커니즘은 자기 자신을 호출하기 때문에

  기저 조건에 도달하지 않으면 중단되지 않고 계속 자기 자신을 호출한다. 재귀로 인한 스택 오버플로는 올바른 기저

  조건을 갖추지 못한 결과일 가능성이 매우 높다.

  그 예로 n부터 0까지 세면서 숫자를 출력하는 다음 함수를 살펴보자.

  위 함수의 기저 조건은 n이 0보다 작거나 같은 경우다. 음수가 입력으로 주어지면 이미 기저 조건에 도달한 것이기

  때문에 어떤 숫자도 출력되지 않는다. 기저 조건 외에도 재귀 함수는 분할 정복 방식을 활용한다.

  2 - 2) 분할 정복 방식

  분할 정복 방식이란 어떤 문제를 작은 단위로 나눠서 해당 작은 단위의 문제들을 모두 해결함으로써 문제를 해결하는 

  것을 말한다. 위 예에서 7, 6, 5, 4, 3, 2, 1, 0을 출력하는 하나하나가 작은 단위인 것이다. 그렇게 작은 문제를 해결하면서

  기저에 도달해야 올바른 재귀적 매커니즘이라 할 수 있다.

  ex) 피보나치 수열의 n번째 숫자를 출력하는 함수를 재귀 함수로 구현해보자.

  기저 경우 : 피보나치 수열의 기저 경우는 첫 번째 항목이 1일 때다.

  분할 정복 : 피보나치 수열의 정의에 따라 n번째 수는 (n-1) 번째 + (n-2) 번째 피보나치 수의 합이다.

  하지만 이러한 구현의 시간 복잡도는 O(2^n)이다. 

  피보나치 수열 : 꼬리 재귀

  꼬리 재귀 함수는 재귀 호출이 함수에서 가장 마지막에 실행되는 방식의 재귀 함수다.

시간 복잡도 : 함수는 n번 실행된다. 재귀 호출이 일어날 때마다 n - 1씩 감소하기 때문이다.

공간 복잡도 : 위의 함수에 사용된 스택 콜 때문에 공간 복잡도 역시 O(n)이다.

이처럼 재귀는 코드를 간결하고 아름답게 만든다!

3. 재귀의 빅오 분석 - 마스터 정리

  마스터 정리는 다음과 같다. a >= 1이고 b >= 1인 T(n) = aT(n/b) + O(n^c)의 형태를 지닌 점화식이 있을 때

  세 가지 경우가 존재한다.

  a는 재귀 호출에 곱해지는 계수다. b는 '로그'항이다. b는 재귀 호출 시에 나누는 항이다. 마지막으로 c는

  등식의 비 재귀 구성 요소에 대한 다항식의 항이다.

*log_{x}{y} : 밑이 x이고 진수가 y인 로그

  3 - 1) 경우 1 : c < log _{b}{a} 이면 O(n^(log _{b}{a}))이다.

  예를 들어 T(n) = 8T(n/2) + 1000n^2이라고 하면 a = 8, b = 2, c = 2이고 2 < log_{2}{8}이니까 T(n) = O(n^3)이다.

  3 - 2) 경우 2 : c = log _{b}{a}이면 T(n) = O(n^c * log(n))이다.

  예를 들어 T(n) = 2T(n/2) + 10n이라고 하면 a = 2, b = 2, c = 1이고 1 =  log_{2}{2}이므로 T(n) = O(n^1 * log(n)) = O(nlogn)

  3 - 3) 경우 3 :  c > log _{b}{a}이면 T(n) = O(f(n))이다.

  예를 들어 T(n) = 2T(n/2) + n^2이라고 해보자. a = 2, b = 2, c = 2이고 2 > log_{2}{2}이므로 T(n) = f(n) = O(n^2)

사실.. 블로킹하면서 본인도 무슨 소리인지 잘 모르겠다. 재귀의 알고리즘 빅오를 분석하는 것은 꽤나 어려운 것 같다.

4. 재귀 호출 스택 메모리

  재귀 함수는 자기 자신을 호출하기 때문에 메모리를 차지한다. 따라서 재귀 함수는 공간 복잡도 또한 신경을 써줘야 한다.

예를 들어 위와 같은 함수는 함수가 n번 호출되므로 공간 복잡도는 O(n)이다.

재귀 함수의 호출은 운영체제의 메모리 스택에 저장돼야 하는데, 이러한 재귀 호출로 인해 발생하는 추가적인 공간 복잡도

비용을 지닌다. 스택은 재귀의 기저 경우가 해결될 때까지 축적된다. 사실 이러한 이유로 인해 재귀 해결책보다 반복 루프를

활용한 해결책을 선호하기도 한다. 최악의 상황으로 기저 경우가 잘못되면 재귀함수는 스택 오버플로 오류로 인해 치명적인

오류를 일으킨다. 스택 오버플로는 메모리 스택에 허용된 수의 항목보다 재귀 호출이 많을 때 일어난다.

5. 요약

  재귀는 복잡한 알고리즘을 구현하기 위한 강력한 도구다. 모든 재귀함수는 기저 경우와 분할 정복 방식으로 구성된다.

  이러한 재귀 알고리즘의 빅오는 경험적으로 수행되거나 마스터 정리를 통해 수행된다. 마스터 정리를 사용하는 경우

  점화식이 필요하고 해당 점화식의 a, b, c를 식별해야 한다. 마지막으로 재귀 함수는 콜 스택에서의 공간을 필요로 한다.

1. 자바스크립트 객체 : 객체 상수 {} 또는 new Object(); 구문을 통해 자바스크립트 객체를 생성할 수 있다.

  추가적인 속성을 추가하거나 속성에 접근하는 방법은 object.propertyName을 사용하거나 object['propertyName']을 사용하면 된다.

2. 프로토타입 활용 상속 : 자바와 같은 대부분의 강 자료형 언어에서는 클래스의 메소드가 클래스와 동시에 정의된다.

  하지만 자바스크립트에서는 함수가 클래스의 자바스크립트 Object 속성으로 추가돼야 한다.

  다음 코드는 this.functionName = function() {}을 사용해 함수를 추가하는 예다.

  위 클래스는 생성자에서 sayName 함수를 동적으로 추가한다. 이러한 패턴을 프로토타입 활용 상속이라고 한다.

  자바스크립트에서 프로토타입 활용 상속은 유일한 상속 방법이다. 클래스의 함수를 추가하기 위해서는 .prototype 속성을

  사용한 다음 함수의 이름을 지정하기만 하면 된다. .prototype 속성을 사용하는 것은 해당 객체의 자바스크립트 Object 속성을

  동적으로 확장하는 것이다. 자바스크립트는 동적이고 클래스는 새로운 함수 멤버를 이후에 필요할 때 추가할 수 있기 때문에

  이러한 방식이 표준이다. 자바와 같은 강 자료형 언어에서는 이러한 방식이 허용되지 않는다!

  다음 코드는 .prototype을 활용한 예이다.

3. 생성자와 변수 : 자바스크립트에서 클래스의 변수가 해당 클래스 객체의 속성이기 때문에 this.propertyName으로 선언된

  모든 속성을 공개적으로 접근할 수 있다. 이는 해당 객체의 속성들을 다른 범위에서도 직접 접근할 수 있다는 의미이다.

  비공개 변수를 흉내내기 위해 this.propertyName을 사용하는 대신 지역 변수를 선언한 다음 해당 변수에 대한 접근을 허용하는

  getter와 setter를 만들 수 있다. 이런 식으로 변수는 해당 생성자의 범위 내에서만 사용 가능하다. 동시에 이러한 비공개 변수를

  흉내 낸 지역 변수들에 접근하기 위해서는 인터페이스 함수들을 정의해야 한다.

4. 요약 : 자바스크립트에서는 프로토타입 활용 상속이 상속에 있어 선호되는 방법이다.

  프로토타입 활용 상속은 .prototype을 통해 신규 함수들을 클래스에 추가함으로써 동작한다.

  자바스크립트는 자바와 달리 비공개 변수를 지원하지 않으므로 생성자 함수의 범위에 한정된

  변수를 생성해야 한다. this키워드를 통해 변수를 선언하면 자동으로 공개 속성이 된다!

*출처 : 자바스크립트로 하는 자료 구조와 알고리즘, 지은이 : 배세민 엔지니어

1. 배열 : 배열은 가장 근간이 되는 자료 구조 중 하나이다. 배열의 중요한 특징은 순서를 가진다는 것이다.

  어떤 자료 구조를 사용하든 개발자들은 4가지 기본 연산(접근, 삽입, 삭제, 검색)과 관련해 시간 복잡도와 공간 복잡도에 관심을 갖는다.

  1 - 1) 삽입 : .push() 메소드를 통해 새로운 항목을 배열 끝에 추가할 수 있다.

                    .unshift() 메소드를 통해 새로운 항목을 배열의 맨 앞에 추가할 수 있다.

  1 - 2) 삭제 : .pop() 메소드를 통해 마지막 항목을 배열에서 삭제할 수 있다.

                    .shift() 메소드를 통해 첫 번째 항목을 배열에서 삭제할 수 있다.

  1 - 3) 접근 : 배열은 인덱스 번호를 통해 해당하는 데이터에 접근할 수 있다.

2. 반복 : 배열의 반복을 다루는 것은 꽤 중요하다. 배열이라는 자료구조상 데이터의 갯수가 많을 것이기 때문이다.

  2 - 1) for문을 이용한 반복

  2 - 2) 내장함수 forEach() : 위의 for문과는 다르게 반복 바깥으로 빠져나오거나 배열 내 특정 항목들을 건너뛸 수 없다!

만약 매개변수로 아무것도 전달하지 않으면 해당 배열의 복사본을 반환한다!

하지만 복사본은 기존의 배열과 메모리 주소가 다르기 때문에 '===' 통해 비교하면 false가 나온다!

  3 - 2) .concat() : 컨캣은 신규 항목을 기존 배열의 맨 뒤에 추가하고 해당 배열을 반환한다!

  3 - 3) .length : length 속성은 배열의 크기를 반환한다. 해당 속성을 더 작은 크기로 변경하면 배열에서 항목들이 제거된다

4. 자바스크립트 함수형 배열 메소드 : 자주 쓰이는 배열의 함수형 메소드는 대표적으로 map, fliter, reduce가 있다.

  4 - 1) map : map 함수는 매개변수로 전달된 함수 변환을 배열의 모든 각각의 항목에 적용한 다음 변환이 적용된 항목들을

  포함하는 신규 배열을 반환한다.

  4 - 2) filter : filter 함수는 배열 내 항목들 중 함수의 매개변수로 전달된 조건을 충족시키는 항목들로만 구성된 배열을 반환한다.

  4 - 3) reduce : reduce 함수는 매개변수로 전달된 변환 함수를 사용해 배열의 모든 항목을 하나의 값으로 결합해 반환한다.

  reduce 함수는 initialValue를 두 번째 인자를 받을 수 있다.

  사실 map, filter, reduce는 매개변수로 함수를 받는다는 점에서 다른 메소드들에 비해 난이도가 조금 높다. 따라서 익숙해지려면

  충분한 연습이 필요하다!! 해당 메소드에 대한 쉬운 예시로 먼저 감을 익혀보자!

  5. 요약 : 배열은 자주 쓰이는 자료구조이므로 배열에 대한 이해와 배열을 처리할 때 자주 쓰이는 메소드에 대해선

  충분히 익숙해지도록 하자! 블로그에 정리한 메소드 외에도 쓸 수 있는 메소드는 많다. 추가적인 메소드는 MDN을 통해

  필요할 때마다 찾아서 쓸 수 있도록 하자

*출처 : 자바스크립트로 하는 자료구조와 알고리즘, 지은이 : 배세민 엔지니어

1. String에 있는 유용한 메소드 정리

  1 - 1) indexOf : 문자열 내에 특정 문자열을 찾기 위해 해당 메소드를 사용할 수 있다.

  .indexOf 메소드는 검색하고자 하는 문자열을 매개변수로 받는다.

  만약 매개변수로 받은 문자열이 존재한다면 문자열이 시작하는 index를 반환하고

  문자열이 존재하지않으면 -1을 반환한다.

  1 - 2) .split(separator) : 문자열을 여러 부분으로 나누기 위해 해당 메소드를 사용할 수 있다.

  split 메소드는 하나의 매개변수를 입력받아 부분 문자열 배열을 생성한다.

  1 - 3) .replace(string, replaceString) : 문자열 변수 내에 특정 문자열을 다른 문자열로 대체한다.

2. 정규 표현식

  2 - 1) 정규 표현식은 검색 패턴을 정의한 문자열들의 집합이다. 자바스크립트에는 정규 표현식에 사용할 수 있는

  기본 객체 RegExp가 포함된다.

  2 - 2) RegExp의 생성자가 받는 매개변수에는 필수 매개변수인 정규 표현식과 선택 매개변수인 일치 관련 설정이 있다.

  다음은 일치 관련 설정 매개변수의 세부 내용이다.

  ---------------------------------------------------------------------------------------------------------

  i : 대소문자를 구별하지 않고 일치하는 문자열을 검색한다.

  g : 전역적으로 일치하는 문자열을 검색한다.(일치하는 문자열을 처음 발견한 이후 멈추는 대신 모든 일치하는 문자열을 찾는다.)

  m : 다중열 문자열에 대해서도 일치하는 문자열을 검색한다.

  2 - 3) RegExp에는 두 가지 함수가 있다.

  search() : 문자열 내에 일치하는 문자열을 찾는다. 일치하는 문자열의 인덱스를 반환한다.

  match() : 일치하는 문자열을 찾는다. 모든 일치하는 문자열을 반환한다.

  2 - 4) 자바스크립트 String 객체에는 정규 표현식과 관련된 다음 두 가지 함수가 있는데 두 함수는 RegExp 객체를 인자로 받는다.

  exec() : 문자열 내에 일치하는 문자열을 찾늗나. 일치하는 첫 번째 문자열을 반환한다.

  test() : 문자열 내에 일치하는 문자열을 찾는다. true 또는 false를 반환한다.

3. 기본 정규 표현식

  3 - 1) ^ : 문자열/줄의 시작을 나타낸다.

  3 - 2) /d : 모든 숫자를 찾는다.

  3 - 3) [abc] : 괄호 내의 모든 문자를 찾는다.

  3 - 4) [^abc] : 괄호 내의 문자들을 제외한 모든 문자를 찾는다.

  3 - 5) [0-9] : 괄호 내의 모든 숫자를 찾는다.

  3 - 6) [^0-9] : 괄호 내의 숫자들을 제외한 모든 숫자를 찾는다.

  3 - 7) (x|y) : x 또는 y를 찾는다.

4. 자주 사용하는 정규 표현식

  정규 표현식은 자바스크립트에서 사용자의 입력이 유효한지 확인할 때 매우 유용하다.

  다음은 개발자들이 자주 사용하는 5가지 정규 표현식이다.

  예시를 통해 알아보자.

1. 유용한 메소드

  1 - 1) Math.floor() : 가장 가까운 정수로 내림한다

  1 - 2) Math.round() : 가장 가까운 정수로 반올림한다.

  1 - 3) Math.ceil() : 가장 가까운 정수로 올림한다.

1. 자바스크립트 범위 : 범위(scope)는 자바스크립트 변수에 대한 접근 권한을 정의하는 것이다. 자바스크립트에서 변수는 전역 범위 또는 지역 범위에 속할 수 있다. 전역변수는 전역 범위에 속하는 변수이고 프로그램의 어디에서나 해당 변수에 접근할 수 있다.

  1 - 1) var를 사용해 선언하기 : 함수 범위

  자바스크립트에서 var는 변수를 선언하는 데 사용하는 키워드다. 변수를 어디에서 선언하든 변수 선언이 함수의 맨 앞으로 이동한다.

  이를 변수 호이스팅(variable hoisting)이라고도 한다. 즉 변수가 스크립트의 가장 마지막에 선언됐다고 하더라도 해당 선언 코드가

  가장 마지막에 실행되는 것이 아니다. 예시를 살펴보자.

  1 - 2) let를 활용한 선언 : 블록 범위

  변수를 선언할 때 사용할 수 있는 또 다른 키워드로는 let이 있다. let을 사용해 선언된 변수는 가장 가까운 블록 범위를 갖는다.

  즉 변수가 선언된 {} 내에서 유효하다! 마찬가지로 예시를 살펴보자.

2. 등가와 형 : 자바스크립트에는 자바와 같은 전통적인 언어와 다른 자료형이 있다.

  2 - 1) 변수형

  자바스크립트에는 boolean, number, string, undefined, object, function, symbol과 같은 일곱개의 자료형이 있다. 여기서 특이한 점은    선언만되고 값이 할당되지 않은 변수에는 undefined가 할당된다는 것이다. typeof는 변수의 형을 반환하는 데 쓰이는 기본 연산자이다.

  2 - 2) 참/거짓 확인

  if문 내에서 참/거짓 확인이 사용된다. 많은 언어들의 경우 if() 함수 내의 매개변수는 boolean형이어야 한다. 하지만 자바스크립트(또는 다    른 동적언어들)는 좀 더 유연하다. 만약 매개변수로 false, 0, 빈 문자열, NaN, undefined, null 값이 온다면 false로 판단되어 {} 내의 구문    을 실행하지 않는다. 그렇지 않고 나머지의 경우는 true로 평가되어 {} 내의 구문을 실행한다. 

  2 - 3) === 대 == 

  자바스크립트는 스크립트 언어이고 변수 선언 시 변수에 형이 할당되지 않는다. 대신에 코드가 실행될 때 해당 변수의 형이 해석된다. 따라    서 ===는 ==보다 등가를 좀 더 엄격히 확인한다. ==는 값만을 확인하는 대신 ===는 형과 값 모두를 확인한다. 

3. 요약

  자바스크립트에는 대부분의 언어들이 사용하지 않는 다른 방식의 변수 선언 방식 존재한다. var는 함수 범위 내에서 변수를 선언하고 let은    블록 범위에서 변수를 선언한다. 마지막으로 등가 확인을 위해 값에 대해서는 ==를 사용하고 값과 형이 모두 같은지 확인하기 위해서는   

 ===를 사용하자. 하지만 ==와 === 연산자는 숫자, 문자열, 불리언과 같은 비객체형에만 사용할 수 있다.

*출처 : 자바스크립트로 하는 자료 구조와 알고리즘, 지은이 : 배세민 엔지니어

1. 빅오 표기법이란? -> O(n)

  1 - 1) 빅오 표기법이란 시간과 공간에서 알고리즘의 복잡도 분석을 표기하는 방법이다.

  1 - 2) 빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정한다.

  1 - 3) 빅오 표기법에서 n은 입력의 개수를 나타낸다.

  1 - 4) 이러한 빅오 표기법으로 해당 알고리즘이 시간과 공간 복잡도에서 얼마나 효율적인지를 판단할 수 있다!

2. 빅오 표기법 규칙

  2 - 1) 계수 법칙 : 어떤 상수 k가 0보다 크다고 할 때, f(n)이 O(g(n))이면 kf(n)은 O(g(n))이다. 이를 계수 법칙이라 한다.

  2 - 2) 합의 법칙 : f(n)이 O(h(n))이고 g(n)이 O(p(n))이면 f(n) + g(n)은 O(h(n) + p(n))이다. 이를 합의 법칙이라 한다.

  2 - 3) 곱의 법칙 : f(n)이 O(h(n))이고 g(n)이 O(p(n))이면 f(n)g(n)은 O(h(n)p(n))이다. 이를 곱의 법칙이라 한다.

  2 - 4) 다항 법칙 : f(n)이 k차 다항식이면 f(n)의 빅오는 O(n^k)이다. 이를 다항 법칙이라 한다.

3. 계수 법칙 : "상수를 제거하라"

  계수 법칙은 가장 이해하기 쉬운 문법이다. 단순히 입력 크기와 연관되지 않은 상수를 전부 무시하면 된다. 

  빅오에서 입력 크기가 클 땐, 계수를 무시할 수 있다.