[ Section 3. 알고리즘 ]

1. 재귀(recursion)

재귀(recursion)

어떤것을 정의할 때 자기 자신을 참조하는 것

재귀함수란

함수 내부에서 자기 자신(함수)를 호출하여 실행하는 함수

→ 함수를 정의할 때 재귀적으로 정의된 함수를 재귀함수 라고 부른다.

기저조건(Base Case)

재귀 함수의 탈출 조건, 재귀 호출을 종료하는 조건을 의미한다.

기저 조건이 없다면 함수는 계속해서 자기 자신을 호출하게 되므로, 무한 루프에 빠져 스택 오버플로우(Stack Overflow)가 발생한다.

콜 스택(Call Stack)

메모리 영역에서 Stack의 한 부분을 의미하며, 재귀 함수는 이 콜 스택을 사용해 실행된다.

재귀함수를 사용하는 케이스

for문에서 재귀함수를 사용하는 것은 비효율적이다.

조금 복잡한 로직들을 구현할 때 재귀함수를 사용 한다. ex) 팩토리얼 계산

2. 재귀적으로 생각하기

재귀함수의 사용패턴 - 1. 반복실행

재귀함수를 반복실행하여 for문 처럼 사용할 수 있다.

그러나 재귀함수로 반복문을 실행하는것은 성능이 좋지 않다.

재귀함수의 사용패턴 - 2. 하위문제의 결과 기반으로 현재 문제 계산

재귀함수는 하위문제의 결과를 기반으로 현재 문제를 해결하는 하향식 계산 방식을 사용한다.

재귀함수에 상향식 계산 방식을 사용하긴 하지만 재귀함수는 하향식 계산 방식을 사용하는데 주로 쓰인다.

상향식 계산

현재 문제 결과를 기반으로 상위 문제를 해결하는 방식

하향식 계산

하위 문제 결과를 기반으로 현재 문제를 해결하는 방식

3. 재귀 - 하노이 탑

재귀함수를 이용하여 하노이탑을 하향식 계산 방식으로 접근

// ch03. 재귀 - 하노이 탑
// ex. 기둥 A 에 있는 원반 3개를 기둥 C 로 이동하려는 경우
//  1) 원반 3이 기둥 C로 옮겨 져야 함 -> [하위 문제] : 원반 1, 2가 기둥 B에 옮겨져야 한다.
//      1-1) 원반 1, 2가 기둥 B에 옮겨져야 한다. -> [하위 문제] : 원반 2가 기둥 B에 옮겨져야 한다.
//      1-1-1) 원반 2가 기둥 B에 옮겨져야 한다. -> [하위 문제] : 원반 1이 기둥 C에 옮겨져야 한다.
function hanoi(count, from, to, temp) { // 3, A, C, c
    if(count === 0) return;
    hanoi(count - 1, from, temp, to);   // 2, A, B, C
    console.log(`원반 [ ${count} ]를 [ ${from} ]에서 [ ${to} ]로 이동`);
    hanoi(count - 1, temp, to, from);   // 2, B(temp), C(to), A(from)
}

// 첫번째 매개변수 : 원반의 개수(count)
// 두번째 매개변수 : 원반들이 처음 꽂혀있는 기둥(from)
// 세번째 매개변수 : 원반들이 최종적으로 꽂힐 기둥(to)
// 네번째 매개변수 : 원반들이 이동을 위해 임시로 사용할 기둥(temp)
hanoi(3, "A", "C", "B");

4. 정렬 - 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)이란

배열의 무작위 순서를 정렬할 때, 앞의 원소와 뒤의 원소를 비교하며 순서를 정렬하는 방식이다.

• 배열의 모든 원소의 앞, 뒤 원소를 비교한다. → 맨 마지막 원소는 가장 큰 원소가 위치한다.

• 정렬된 마지막 원소를 제외하고 나머지 원소의 앞, 뒤 원소를 비교한다.

• 정렬은 배열 길이 - 1 만큼 실행한다.

// ch04. 정렬 - 버블정렬(Bubble Sort)
function BubbleSort(arr) {
    console.log(`arr.length ===> [${arr.length}]`);
    // 자리의 교체는 arr.length -1 만큼 진행
    for(let i = 0; i < arr.length - 1; i++) {
        console.log(`1) [${i}]번째 for문`);
        // 정렬이 된 원소의 이전 원소보다 하나 이전의 원소까지 순회
        for(let j = 0; j < (arr.length - i - 1); j ++){
            console.log(`2) [${j}]번째 for문`);
            // 실제로 값을 비교하며 배열 원소의 값을 바꿔준다.
            console.log(`3) arr[j] 값 ===> ${arr[j]}`);
            console.log(`3) arr[j+1] 값 ===> ${arr[j+1]}`);
            if(arr[j] > arr[j + 1]){ // 앞의 원소값이 뒤의 원소값 보다 큰 경우
                console.log(`4) arr[j]값이 arr[j+1] 값 보다 큽니다! ${arr[j]} > ${arr[j+1]}`);
                let temp = arr[j];  // 1) 앞의 원소 값을 임시로 저장
                arr[j] = arr[j + 1] // 2) 뒤의 원소 값을 앞의 원소값으로 변경
                arr[j + 1] = temp;  // 3) 뒤의 원소 값을 임시로 저장했던 값으로 변경
            }
            console.log(`5) ${arr}`);
        }
    }
}

버블 정렬의 성능

버블정렬의 성능을 수학식으로 풀어쓰면 등차수열의 합과 같다.

이때 빅 오는 O(n²)이 된다. 데이터가 증가하면 계산량이 증가하여 성능이 떨어지므로 복잡한 시스템에 적합하지 않은 계산법이다.

버블 정렬의 장단점

장점

• 단순하고 직관적이라 구현이 쉬운 알고리즘이다.

단점

• 계산량이 증가시 성능이 떨어지기 때문에 복잡한 시스템에 적합하지 않다.

5. 정렬 - 선택 정렬(Selection Sort)

선택 정렬이란?

정렬되지 않은 영역의 원소들을 순회하며 제일 작은 값을 찾아 순회 범위의 첫번째 원소에 위치 시키는 정렬 알고리즘

선택 정렬의 성능

선택 정렬의 빅 오는 O(n²)이 된다. 버블 정렬과 마찬가지로 성능이 떨어지므로 복잡한 시스템에 적합하지 않은 계산법이다.

선택 정렬의 장단점

장점

• 단순하고 직관적이라 구현이 쉬운 알고리즘이다.

단점

• 계산량이 증가시 성능이 떨어지기 때문에 복잡한 시스템에 적합하지 않다.