2020/10/05 - TIL (재귀, DOM, 복잡도)

오늘 했던 일

• 재귀 함수
• element.childNodes, element.classList
• 복잡도

 

 

 

재귀란?

컴퓨터 과학에 있어서 재귀(Recursion)는 자신을 정의할 때 자기 자신을 재 참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다.

 

재귀 함수

재귀 함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다. 다른 말로는 재귀 호출, 되부름이라고 부르기도 하며, 반복문을 사용하는 코드는 항상 재귀 함수를 통해 구현하는 것이 가능하며 그 반대도 가능하다.

 

재귀 함수를 작성할 때는 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 한다는 부분을 인지하고 작성하면 무한 루프를 방지할 수 있습니다.

 

 

 

팩토리얼 구하기

function factorial(n){
  if(n === 1){
    return 1;
  }
  return n * factorial(n-1);
}

factorial(3); //6

팩토리얼 함수에 3의 값을 넣었을 때 처음 스택 3이 쌓이고 두 번째 2 마지막 조건문을 끝으로 1이 쌓입니다.

 

 

재귀는 언제 사용하는 게 좋을까?

1. 주어진 문제가(구조는 비슷하고) 더 작은 문제로 나누어질 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

 

 

 

element.childNodes

childNodes는 주어진 요소의 자식 노드 모음(collection)을 반환합니다.

 

// body는 <boby>요소

if(body.hasChildNodes()){ //body의 자식요소가 있는지 검사
  let childern = boby.childNodes;
  for(let i = 0; i < children.length; i++){
    //children[i]로 각자식에 무언가를 함
  }
} 

 

 

element.classList

element.classList는 엘리먼트의 클래스 속성의 컬렉션인 DOMTokenLIst를 반환하는 읽기 전용 프로퍼티이다.

 

메소드

• add( String [, String [,...]] )
  지정한 클래스 값을 추가한다. 만약 추가하려는 클래스가 엘리먼트의 class 속성에 미이 존재한다면 무시한다.
• remove( String [, String [,...]] )
  지정한 클래스 값을 제거한다.
• item(Number)
  컬렉션의 인덱스를 이용하여 클래스 값을 반환한다.
• toggle( String, [, force] )
  하나의 인수만 있을 때 : 클래스 값을 토글링한다. 즉, 클래스가 존재한다면 제거하고 false를 반환하며, 존재하지 않으면 클래스를 추가하고 true를 반환한다.
• contains( String )
  지정한 클래스 값이 엘리먼트 class 속성에 존재하는지 확인한다.
• replace( oldClass, newClass)
  존재하는 클래스를 새로운 클래스로 교체한다.

 

 

시간 복잡도(Time Complexity)

 

시간 복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는지를 센 결과에 각 명령어의 실행시간을 곱한 합계를 의미한다.

그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 된다. 또한, 알고리즘의 분석은 일반적으로 공간 복잡도보다는 시간 복잡도를 통해서 이루어진다.

 

시간 복잡도를 표기하는 방법 중 BIG-O 표기법이 있는데, 이는 실행 시간 n을 O(n)으로 표기한다.

BIG-O에서 차수가 가장 높은 최고차 항만 두고 나머지는 버린다.

 

 

1. O(1) : 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다.
   (ConstTime)
   입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다.
   알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.
2. O(n) : 입력 데이터의 크기에 비례하여 처리시간에 걸리는 알고리즘을 표현할 때 사용
   (LinearTime)
   데이터양에 따라 시간이 정비례한다.
   Linear search, for 문을 통한 탐색을 생각하면 된다.
3. O(n^2):Quadratic TIme
   데이터 양에 따라 걸리는 시간은 제곱에 비례한다.(효율이 좋지 않음, 사용 x)
   해당 유형은 이중 Loop내에서 입력 자료를 처리하는 경우에 나타난다. n값이 큰 값이 되면 실행시간은 감당하지 못할 정도로 커지게 된다.
   문제를 해결하기 위한 단계의 수는 입력값 n의 제곱
4. O(log n ): Binary search tree access(이진 검색) - search(검색), insertion(삽입), deletion(삭제)
   데이터양이 많아져도, 시간이 조금씩 늘어난다.
   시간에 비레하여, 탐색 가능한 데이터양이 2의 n승이 된다.
   문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
   만약 입력 자료의 수에 따라 실행 시간이 이 log n의 관례를 만족한다면 n이 증가함에 따라 실행시간이 조금씩 늘어난다. 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형이다.

 

자료구조별 시간 복잡도 분석

 

 

 

 

앞으로 해야 할 일

• Recursion 과제 마무리하기
• H/A 대비하여 복습하기