자료구조와 알고리즘

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

1) 버블정렬 : O(n²)

• 장점 : 이해와 구현이 쉬움

• 단점 : 성능이 O(n²)으로 좋지 않음

2) 선택정렬 : O(n²)

• 장점 : 이해와 구현이 쉬움

• 단점 : 성능이 O(n²)으로 좋지 않음

3) 삽입정렬 : O(n²)

• 장점 : 이해와 구현이 쉬움

• 단점 : 성능이 O(n²)으로 좋지 않음

4) 병합정렬 : O(nlogn)

• 장점 : O(nlogn)으로 성능이 좋음

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

5) 퀵정렬 : O(nlogn)

• 장점 : O(nlogn)으로 성능이 좋음

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

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

✨️ 타뷸레이션을 사용할 것 같습니다. 재귀로 쉽게 구현이 가능하더라도 메모리가 부족한 상황에서, 메모리를 사용하여 성능을 올리는 메모이제이션은 오히려 성능을 더 떨어 뜨릴 것으로 보이기 때문에 적합하지 않아 보입니다. 

타뷸레이션은 상향식이지만, 메모제이션보다 적은 메모리와 빠른 속도로 빠르게 해결할 수 있기 때문입니다.