워밍업 클럽 CS 2주차 발자국 : 자료구조와 알고리즘

알고리즘

재귀 (Recursion)

재귀란, 어떤 대상을 정의할 때 그 대상이 자기 자신을 참조하는 개념을 말합니다. 이를 함수로 구현한 것을 재귀 함수라고 합니다.

• 재귀 함수: 자신을 재귀적으로 호출하는 함수.

  • 기저 조건(탈출 조건): 재귀 함수가 무한히 호출되지 않도록 종료 조건이 반드시 필요합니다.

    • 기저 조건이 없다면, 함수는 계속 호출되며, 결국 콜스택(Call Stack)이라는 메모리 공간이 꽉 차고 프로그램은 강제로 종료됩니다.

*콜스택(Call Stack) : 함수 호출 시 해당 함수의 실행 정보를 저장하는 메모리 영역입니다. 스택(Stack) 구조로, 먼저 호출된 함수가 나중에 종료되는 후입선출(LIFO) 방식으로 동작합니다.

재귀적으로 문제 해결하기

패턴

1. 단순한 반복 실행

    

   • 단순 반복 작업은 재귀로 구현했을 때 성능 상의 이점이 없습니다. 오히려 반복문보다 더 많은 메모리를 차지하게 됩니다.
     반복 작업은 재귀보다는 반복문이 더 효율적입니다.

    

2. 하위 문제를 기반으로 현재 문제 계산

   • 하향식 계산 방식으로 문제를 해결하는 경우 재귀가 더 유리합니다.

   • 예시: 팩토리얼 함수는 재귀를 이용한 하향식 계산이 가능합니다.

   • 같은 문제를 반복문으로 해결할 수도 있지만, 이때는 상향식 계산 방식이 주로 사용됩니다.

재귀 함수는 특히 하향식 계산에서 강력한 성능을 발휘합니다. 이 방식은 재귀를 통해서만 구현할 수 있습니다.

function hanoi(count = number, from = string, to = string, tmp = string) {
	if(count === 0) return;
	hanoi(count - 1, from, tmp, to);
	console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`);
	hanoi(count - 1, tmp, to, from);
}

hanoi(3, 'A', 'C', 'B');

버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 원소를 비교하고, 크기에 따라 자리를 바꾸는 방식으로 정렬을 수행하는 알고리즘입니다.

• 성능: 시간 복잡도는 최악의 경우 O(n2)O(n^2)O(n2).

• 장점: 이해하기 쉽고 구현이 간단한 알고리즘입니다.

• 단점: 효율이 좋지 않아, 실무에서 자주 사용되지 않습니다.

   

function bubbleSort(arr) {
	for(let i = 0; i < arr.lenght - 1; i++) {
		for(let j = 0; j < (arr.length - i - 1); j++) {
			if(arr[j] > arr[j + 1]) {
				let temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

선택 정렬 (Selection Sort)

선택 정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾아 첫 번째 원소와 교체하는 방식으로 정렬하는 알고리즘입니다.

• 성능: 시간 복잡도는 최악의 경우 O(n2)O(n^2)O(n2).

• 장점: 구현이 단순하며 이해하기 쉽습니다.

• 단점: 성능이 좋지 않아, 대규모 데이터에 적합하지 않습니다.

   

   

  function selectSort(arr) {
  	for(let i = 0; i < arr.length; i++) {
  		let minValueIndex = i;
  		
  		for(let j = i + 1; j < arr.length; j++) {
  			if(arr[j] < arr[minValueIndex]) {
  				minValueIndex = j;
  			}
  		}
  		
  		let temp = arr[i];
  		arr[i] = arr[minValueIndex];
  		arr[minValueIndex] = temp;
  	}
  }