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

• 퀵 정렬 - O(n log n)

  • 장점은 성능이 우수하며 정렬이 빠르다. 하지만 단점으론 이해와 구현이 어렵다.

  • 특히 퀵 정렬의 경우 병합 정렬과 달리 피벗이 배열을 반으로 가르지 않고, 한쪽에 쏠리게 되면 복잡도는 O(n^2)을 가지게 되어 정렬이 매우 느린 상황이 발생할 수 있다.

• 병합정렬 - O(n log n)

  • 장점은 성능이 우수하며 정렬이 빠르다.

  • 단점으론 이해와 구현이 어렵다.

• 삽입정렬,선택정렬,버블정렬 - O(n^2)

  • 장점으론 병합, 퀵 정렬에 비해 이해와 구현이 쉽다.

  • 단점은 병합정렬과 퀵 정렬에 비해 상대적으로 느린 속도를 갖는다.

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

• 타뷸레이션을 사용하는게 좋다.

• 메모이제이션은 기존의 재귀와 달리 계산에 사용되는 값들을 저장해 놓는 방식이다. 이 저장으로 메모리를 통해 성능을 향상시킨다. 하지만 성능을 위해 메모리를 사용해서 저장한다. 비록 분할 정복을 해결 할때 재귀가 직관적이라면 메모이제이션이 더 유리하지만 메모리가 부족한 시스템이라면 메모리도 절약하면서 속도 역시 빠른 타뷸레이션을 사용하는게 더 좋은 방법이라고 생각한다.