📚 수학 기본 이론

📊 알고리즘 복잡도

📈 알고리즘 성능 평가 지표

• 정확성
• 작업량
• 메모리 사용량
• 최족성
• 효율성
  • 시간 복잡도
  • 공간 복잡도

---

⏱️ 시간 복잡도

• 입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행 시간을 평가하는 방법

• 3가지 점근적 표현범

  • O(빅오) : 최악의 상황을 고려하여 성능 측정결과표현

    function big_O(n){
        let sum = 0;
        sum = n *2;
        return sum;
    }
    3 -> O(1)
    
    function big_O(arr, n){
        let sum = 0;
        for(let i = 0 ; i < n; i++){
            sum+= arr[i];
        }
        return sum;
    }
    n+2 -> O(N)
    
    function big_O(arr, n){
        let sum = 0;
        for(let i = 0 ; i < n; i++){
            for(let j = 0; j < n ; j++){
                sum+= arr[i][j];
            }
        }
        return sum;
    }
    n²+2 -> O(N²)
    n의 크기가 커질 수록 느려진다
    
    function big_O(arr, n){
        let sum = 0;
        for(let i = 0 ; i < n; i*=2){
            sum+=2
        }
        return sum;
    }
    n/2+2 -> O(logN)

  • 병합 정렬, 분할 정복할 때 logN이 많이 나온다

  • logN 많으면 많을 수록 특정 이상 값이 안올라간다

  • N 보다 빠른 알고리즘을 가지고있다.

  • θ(세타) : 평균적인 경우에서의 성능 측정결과표현

  • Ω(오메가) : 최선의 상황일 때의 성능 측정결과표현

---

🔢 경우의 수

• 어떤 사건 혹은 일이 일어날 수 있는 경우의 가짓수를 수로 표현
• 완전 탐색으로 경우의 수를 푸는 알고리즘
  • 순열
  • 조합
  • 중복 순열

🔁 순열(Permutation)

서로 다른 n개의 원소 중에서 r개를 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수(nPr)

🧩 3개의 알파벳으로 단어를 만드는 경우의 수

let input = ["a", "b", "c"];
let count = 0;

// s: 지금 바꿀 위치(=고정할 자리), r : 마지막 고정할 자리 (여기선 2 → 0~2까지 총 3개 자리 고정)
function permutation(arr, s, r){
    // 1. 재귀함수를 멈춰야할 조건
    if(s == r){
        count++;
        console.log(arr.join(" "));
        return;
    }
    // 2. 재귀를 돌변서 변경되어야 될 부분/메인로직
    for(let i = s; i < arr.length ; i++){
        [arr[s], arr[i]] = [arr[i], arr[s]]; // swap
        permutation(arr, s+1, r); // 요소 선택시 재귀함수 호출
        [arr[s], arr[i]] = [arr[i], arr[s]]; // swap 원상복구
    }

    /**
     s  r
     0  2   i=0 ["a",]
     1  2   i=1 ["a","b", ]
     2  2   ["a","b","c"]
     ...
     1  2   i=2 ["a","c",]
     2  2   ["a","c","b"]
     1  2   i=2 ["a","b",]
     ...
     0  2   i=1 ["b","a","c"]
     ...
     0  2   i=0 ["c",]
     */
}

permutation(input, 0, 2);
console.log(count)

--------------------------------------------------
OUTPUT
a b c
a c b
b a c
b c a
c b a
c a b
6

---

🤝 조합(Combination)

서로 다른 n개의 원소중에서 r개를 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수(nCr)

🃏 4개의 숫자 카드에서 2개를 뽑는 경우의 수

• for문

let input = [1,2,3,4]; // 4C2
let count = 0;

function combination(arr){
    // for -> 뽑는 갯수 ==> r ==> 2
    for(let i = 0; i < arr.length; i++){
        for(let j = i + 1; j<arr.length; j++){
            count++;
            console.log(arr[i],arr[j])
        }
    }
}

combination(input, 0, 2);
console.log(count)

--------------------------------------------------
OUTPUT
1 2
1 3
1 4
2 3
2 4
3 4
6

• 재귀 함수

let input = [1,2,3,4]; // 4C2
let output = [];
let count = 0;

function combination(arr, data, s, idx, r){
    if(s == r){
        count++;
        console.log(data)
        return;
    }
    for(let i = idx; arr.length - i >= r - s ; i++){
        data[s] = arr[i]
        combination(arr, data, s + 1, i + 1, r)
    }
}

combination(input, output, 0, 0, 2);
console.log(count)

--------------------------------------------------
OUTPUT
[ 1, 2 ]
[ 1, 3 ]
[ 1, 4 ]
[ 2, 3 ]
[ 2, 4 ]
[ 3, 4 ]
6

---

🧮 점화식

점화식(재귀식)이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식

• 등차수열 : F(n) = F(n-1)+a // a : 고정된 상수

//등차 수열 - for 문
let result;

function forloop(s, t, number){
    let acc = 0;

    for(let i = 1; i <=number ; i++){
        if( i == 1) {
            acc += s;
        } else{
            acc += t;
        }
        console.log(i, acc)
    }
    return acc;
};

result = forloop(3, 2, 5)
console.log(result)

--------------------------------------------------
OUTPUT
1 3
2 5
3 7
4 9
5 11
11
--------------------------------------------------
--------------------------------------------------

//등차 수열 - 재귀 함수
let result;

function recursive(s, t, number){
    // 멈출 조간
    if( number == 1){
        return s;
    }

    // 반복할 코드
    return recursive(s, t, number-1) + t;
};

result = recursive(3, 2, 5)
console.log(result)

--------------------------------------------------
OUTPUT
11

number : 5 recursive(s, t, 4) + 2 => 9+2 => 11
number : 4 recursive(s, t, 3) + 2 => 7+2 => 9
number : 3 recursive(s, t, 2) + 2 => 5+2 => 7
number : 2 recursive(s, t, 1) + 2 => 3+2 => 5
number : 1 recursive(s, t, 1) + 2 => 3

• 등비수열 : F(n) = F(n-1)*a

  ⇒ 등차수열 공식에서 + → *로 바꾸면된다.

• 팩토리얼 : F(n) = F(n-1)*n

    let reuslt;

    function recursive(number){
        if(number == 1){
            return number;
        }
        return recursive(number-1)*number;
    }

    reuslt = recursive(5);
    console.log(reuslt)

    --------------------------------------------------
    OUTPUT
    120
    5! = 5 X 4 X 3 X 2 X 1

    --------------------------------------------------
    --------------------------------------------------
    let reuslt;

    function recursive(number){
      let hap = 1;
      for( let i = 1 ; i <= number; i++){
        hap *= i;
      }
      return hap;
    }

    reuslt = recursive(5);
    console.log(reuslt)

    --------------------------------------------------
    OUTPUT
    120

• 피보나치 수열 : F(n) = F(n-1)+F(n-2)

  let reuslt;
  
  function recursive(number){
    if(number == 1|| number == 0){
      return number;
    }
  
    return recursive(number - 1)+(number -2);
  }
  
  reuslt = recursive(5);
  console.log(reuslt)
  
    --------------------------------------------------
  OUTPUT
  5
  
  f(5) = f(4) + f(3) => 2 + 3 = 5
  f(4) = f(3) + f(2) => 1 + 2 = 3
  f(3) = f(2) + f(1) => 1 + 1 = 2
  f(2) = f(1) + f(0) => 1 + 0 = 1
  f(1) = 1
  f(0) = 0