수학 기본 이론

경우의 수

어떤 사건 혹은 일이 일어날 수 있는 경우이 수를 가짓수로 표현

완전탐색으로 경우의 수를 푸는 알고리즘

1. 순열 : 서로 다른 n개의 원소중에서 r개를 중복없이 골라 순서에 상관 있게 나열하는 수 (nPr = n!/(n-r)!)
2. 조합 : 서로 다른 n개의 원소중에서 r개를 중복없이 골라 순서에 상관 없이 나열하는 수 (nCr = n!/(n-r)!r!)

순열

방법 1. for문 사용

단점 : r의 수 와 동일한 for문을 가져야되기 때문에 r의 수가 커질수록 구현하기 힘들다.

let arr = ['a','b','c'];
// 첫번째 [i,0,0]
for(let i=0; i<arr.length; i++){
	// [i,j,0]
	for(let j=0; j<arr.length; j++){
    	if(i===j) continue;
		// [i,j,k]
		for(let k=0; k<arr.length; k++){
			if(i===k) continue;
            if(j===k) continue;
            console.log(arr[i],arr[j],arr[k])
		}
    }
}

방법 2. 재귀

for문의 문제를 해결할 수 있다.

let input = ["a", "b", "c"];
function permutation(arr, s, r) {
  if (s === r) {
    count++;
    console.log(arr.join(" "));
    return;
  }
  for (let i = s; i < arr.length; i++) {
    [arr[s], arr[i]] = [arr[i], arr[s]];
    permutation(arr, s + 1, r);
    [arr[s], arr[i]] = [arr[i], arr[s]];
  }
}
permutation(input, 0, 2);

조합

방법 1. for문 사용

순열과 마찬가지로 r의 수만큼 for문을 사용하기 때문에 패스

방법 2. 재귀

function solution(n,r){
    let tmp = Array.from({length:r},()=>0)
    let answer = []
    // l은 뽑은 개수를 나타냄 
    function DFS(l,s){
        if(l===r){
            answer.push(tmp.slice())
        }else{
            for(let i=s; i<=n;i++){
                tmp[l]=i
                DFS(l+1,i+1)
            }
        }
    }
    DFS(0,1)
}
solution(4,2)

점화식 (재귀식)

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

1. 등차 수열 : F(n) = F(n-1) + a (고정된 수)
2. 등비 수열 : F(n) = F(n-1) * a
3. 팩토리얼 : F(n) = F(n-1) * n
4. 피보나치 수열 : F(n) = F(n-1) + F(n-2)

등차 수열

방법 1. for문 사용

// s : 시작값, a : 고정값
function test(s,a,n){
    let acc = 0
    for(let i=0;i<n;i++){
        if(i===1){
            acc+=s
        }else{
            acc+=a
        }
    }
    return acc
}
test(3,2,5)

방법 2. 재귀 사용

function test(s,a,n){
    if(n===1) return s
    return test(s,a,n-1) + a
}
test(3,2,5)
// n=5 : 9 + 2
// n=4 : 7 + 2
// n=3 : 5 + 2
// n=2 : 3 + 2
// n=1 : 3

등비 수열

방법 1. for문 사용

// s : 시작값, a : 고정값
function test(s,a,n){
    let acc = 0
    for(let i=0;i<n;i++){
        if(i===1){
            acc*=s
        }else{
            acc*=a
        }
    }
    return acc
}
test(3,2,5)

방법 2.재귀 사용

function test(s,a,n){
    if(n===1) return s
    return test(s,a,n-1) * a
}
test(3,2,5)

팩토리얼

방법 1. 재귀

function test(n){
    if(n===1) return 1
    return test(n-1) * n
}
test(5)

피보나치

전 항과 전전 항의 값이 현재 항의 값이다.
f(5) : f(4) + f(3)
f(4) : f(3) + f(2)

방법 1. 재귀

function test(n){
    if(n===0 || n===1) return n 
    return test(n-1) + test(n-2)
}
test(5)