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

버블 정렬은 바로 옆에 숫자와 비교해서 자리를 바꾸는 알고리즘으로, 한번 끝까지 진행하면 가장 큰 숫자는 자기 위치를 찾아서 가장 끝에 정렬된다.

이해와 구현이 간단하지만 O(n^2)의 시간복잡도를 가져서 성능이 별로 안좋다.

선택 정렬은 배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교하여 가장 작은 값을 첫 번째 원소로 가져온다.

역시 이해와 구현이 간단하지만 O(n^2)의 시간복잡도를 가져서 성능이 별로 안좋다.

삽입 정렬은 배열을 정렬,비정렬 영역으로 나눠서 정렬한다.

정렬되지 않은 영역에서 데이터를 꺼내고, 정렬된 영역 내의 적절한 위치에 삽입하여 정렬한다.

마찬가지로 구현이 쉽지만, O(n^2)의 시간복잡도를 가져서 성능이 별로 안좋다.

병합 정렬은 분할정복의 방식을 따라서, 큰 문제를 작은 문제로 쪼개서 하나씩 해결한다.

쉽게 병렬화되어 처리할 수 있고, O(n log n)의 시간복잡도를 얻기 때문에 다른 정렬에 비해 이득을 볼 수 있다.

하지만 높은 메모리 사용량이 필요하고 분석하기가 어렵다.

퀵 정렬도 분할정복 방식을 따른다. 정렬 전에 하나의 원소를 피벗으로 설정하여 피벗보다 크고 작은 값을 기준으로 left, right index 영역으로 구분한다. 즉, 한 번 진행이 될 때 마다 피벗이 정렬되고, 왼쪽 오른쪽 영역을 재귀호출하여 모든 영역을 정렬한다.

O(n log n)의 시간복잡도로 병합 정렬과 같아보이지만, 퀵정렬이 더 적은 비교랑 메모리 공간을 차지하기 때문에 퀵 정렬이 더 좋은 알고리즘으로 평가된다. 하지만 피벗을 어떤 것으로 지정하냐에 따라 왼쪽 오른쪽 영역이 한쪽으로 치우칠 수 있기 때문에 최악의 상황으로 O(n^2)이 될 수도 있다.

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

우리가 해결해야 하는 것은 메모리가 부족한 상황을 해결해야 하는 것이므로 타뷸레이션을 사용할 것이다.

재귀로 쉽게 구현이 가능하다는 판단이 있어도 메모이제이션을 사용한다면 여러 재귀호출로 인해 오히려 메모리를 더 많이 사용하게 될 것이기 때문이다.