[워밍업 클럽 3기] CS 2주차 - 발자국

재귀

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

재귀적으로 정의된 함수 → 재귀함수

콜스택

함수가 호출되면서 올라가는 메모리 영역 → 스택이라고도 부름

First In Last Out

for문으로 처리할 수 있는 작업을 재귀함수로 처리한다면 더 비효율적인 상황이 생김

→ 재귀함수가 더 많은 메모리 공간 차지

대신, 재귀함수를 사용하면 처리하기 쉬운 예도 있음. ex) 팩토리얼

패턴 1. 단순 반복 실행

반복문 구현보다 큰 이점은 없음. 콜스택 공간을 많이 차지해 오히려 성능 저하

패턴 2. 하위 문제 결과를 기반으로 현재 문제 계산

예) 팩토리얼, 하노이탑

for 문을 이용한 계산 - 상향식 계산

재귀를 이용해 하위 문제 계산 - 하향식 계산 (상향식도 구현 가능하지만 성능 발휘는 딱히 X)

// 재귀를 이용한 상향식 계산
function factorial2(number, i = 1, sum = 1) {
	if (i > number) return sum;
	return factorial2(number, i + 1, sum * i);
}

정렬 알고리즘

버블 정렬(Bubble Sort)

앞에 있는 숫자와 옆에 숫자를 비교해서 자리를 바꾸는 알고리즘

• 장점: 이해 및 구현 간단

• 단점: 성능이 좋지 않음

성능 - O(n^2)

(n-1) + (n-2) + (n-3) … + 2 + 1 → 등차수열

n(n-1)/2 → (n^2 - n)/2

선택 정렬(Selection Sort)

배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져옴

• 장점: 이해 및 구현 간단

• 단점: 성능이 좋지 않음

성능 - O(n^2)

(n-1) + (n-2) + (n-3) … + 2 + 1 → 등차수열

n(n-1)/2 → (n^2 - n)/2