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

버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort)은 모두 구현이 쉬운 편에 속하나 성능은 약 O(n^2)로 매우 낮습니다. 병합 정렬(Merge Sort)은 재귀적으로 구현해야 하므로 이해와 구현이 어려우나, 성능은 약 O(nlogn)으로 방금 언급한 세 정렬들보다 매우 높습니다. 퀵 정렬(Quick Sort) 또한 병합 정렬과 마찬가지로 Devide & Conquer 방식의 알고리즘으로 평균적으로 약 Θ(nlogn)의 성능을 보이나, 각 단계에서 Pivot이 배열의 요소 중 가장 작은 값 또는 가장 큰 값으로 선정되는 최악의 경우에는 약 O(n^2)로 성능이 결정됩니다. 그러나, 같은 배열을 퀵 정렬과 병합 정렬로 구현했을 때 같은 약 O(nlogn)의 시간 복잡도를 갖는 경우, 참조 지역성(Locality of Reference)의 원리에 의해 퀵 정렬이 병합 정렬보다 처리 속도가 더 빠릅니다.

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

타뷸레이션(Tabulation)을 활용할 것 같습니다. 아니, 문제의 경우(메모리가 부족한 시스템)라면 타뷸레이션밖에 사용할 수 없습니다. 기본적으로 재귀로 쉽게 해결이 가능한 문제라면 일부 특수한 경우를 제외하면 메모이제이션과 타뷸레이션 모두 활용할 수 있습니다. 이 경우, 재귀 호출을 하지 않으므로 공간 복잡도도 낮고, Call Stack 생성/제거 과정에서의 Overhead가 없어 시간 효율성(Time Effeciency)도 높은 타뷸레이션을 사용하는 것이 더 좋습니다. 물론 재귀적 풀이 과정이 더 가독성이 좋을 때, 계산 가능한 경우의 수에 비해 실제 연산에 쓰이는 연산값은 매우 적을 때 등 메모이제이션이 더 좋을 때도 있을 것입니다. 하지만 메모리가 부족한 시스템이라면 메모이제이션으로 해결하려 할 시 Stack Overflow 에러로 인해 문제 해결 자체가 불가능해질 수 있으므로 타뷸레이션을 활용해야 합니다.