1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.

버블 정렬

• 시간 복잡도: O(n^2)

• 장점: 이해와 구현이 간단함

• 단점: 성능이 좋지 않다.

   

   

선택 정렬

• 시간 복잡도: O(n²)

• 장점: 이해와 구현이 간단함

• 단점: 성능이 좋지 않다.

삽입 정렬

• 시간 복잡도: O(n²)

• 장점: 이해와 구현이 간단함

• 단점: 성능이 좋지 않다.

병합 정렬

• 시간 복잡도: O(nlogn)

• 장점: 성능이 좋음

• 단점: 이해와 구현이 어려움

퀵 정렬

• 시간 복잡도: Θ(nlogn)

• 장점: 평균적으로 매우 빠름

• 단점: 최악의 경우 O(n²)으로 성능이 떨어질 수 있음

2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.

타뷸레이션을 사용할 것입니다. 메모이제이션을 사용할 경우 재귀 호출로 인해 스택을 사용하므로, 스택 오버플로우가 발생할 위험이 있습니다. 반면, 타뷸레이션은 반복문을 활용하여 테이블을 채워나가는 방식이므로 스택을 사용하지 않아 추가적인 메모리 소비를 줄일 수 있습니다. 또한, 타뷸레이션은 불필요한 함수 호출 없이 순차적으로 계산을 진행하므로 실행 속도 면에서도 더 효율적일 수 있습니다. 이러한 이유로, 메모리가 부족한 환경에서는 타뷸레이션을 사용하는 것이 더 적절할 것같습니다.