오늘의 TMI
순열과 조합, 점화식은 모두 for문과 재귀로 구현할 수 있었다.
확실히 이번에 두 가지 방법 모두로 구현하면서 느낀 점은 for문은 너무나도 익숙하게 잘 사용했지만 재귀를 구현하는 능력은 약하다는 것이다.
재귀로 구현하는 방식이 익숙하지 않았고, 시간이 비교적 오래걸렸다.
평소의 나라면 설명을 듣고 그냥 넘어갔겠지만 코딩을 하는데 있어서 왜? 라는 물음은 매우 중요했다.
선생님 설명을 듣기 전에 내가 직접 모두 재귀로 구현해보고, 이해가 되지 않는 부분은 그림으로 그려가며 이해할 수 있도록 노력했다.
물론 이해하는 데까지 시간이 오래 걸리고, 다시 보면 또 이해하지 못할지도 모르지만 여러번 반복해서 재귀를 구현하면서 익숙해질 예정이다.

---

순열

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

순열을 만드는 방법은 for문과 재귀, 두 가지 방법이 있다.

for문

만약 3개를 뽑는다고 하면 for문을 3번 중첩해서, 10개를 뽑는다면 10번을 중첩해서 만들어야한다.

⇒ 뽑는 개수에 따라 for문이 많이 중첩되게 되면 효율성이 떨어지기 때문에 재귀를 통해서 많이 구현한다.

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

function permutation(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (i == j) continue;
            for (let k = 0; k < arr.length; k++) {
                if (i == k) continue;
                if (j == k) continue;
                console.log(`${arr[i]} ${arr[j]} ${arr[k]}`);
                count++;
            }
        }
    }    
}

permutation(input);
console.log(count);

// a b c
// a c b
// b a c
// b c a
// c a b
// c b a
// 6

재귀

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

function permuation(arr, s, r) {
    if (s == r) {
        count++;
        console.log(arr.join(" "));
        return;
    }

    for (let i = s; i < arr.length; i++) { // 선택된 것은 뽑지 않게 0에서 s로 변경
        [arr[i], arr[s]] = [arr[s], arr[i]]; //swap
        permuation(arr, s + 1, r); // 첫번째 요소를 선택했으니 두번째 위치를 선택하라는 의미
        [arr[s], arr[i]] = [arr[i], arr[s]]; // 원상복귀
    }
}

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

조합

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

for문

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

function combination(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++){
            count++;
            console.log(`${arr[i]} ${arr[j]}`);
        }
    }
};

combination(input);
console.log(count);

재귀

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

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, idx + 1, r);
    }
}
combination(input, output, 0, 0, 2);
console.log(count);

점화식(=재귀식)

등차수열

등차수열이 일정한 수의 증감을 통해서 값이 바뀌는 것처럼, 등비수열은 일정한 수의 곱셈과 나눗셈을 통해서 값이 바뀌는 것이기 때문에 구현방식이 크게 다르지 않다.

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);

재귀

let result;
let i = 1;

function recursive(s, t, number) { // 3, 2, 5
    if (number == 1) {
        return s;
    }
    return recursive(s, t, number - 1) + t;
}

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

팩토리얼

재귀를 이용한 방식

let result;

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

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

피보나치 수열

재귀를 이용한 방식

let input;

function recursive(number) {
    if (number == 1 || number == 0) {
        return number;
    }
    return recursive(number - 1) + recursive(number - 2);
}

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