[인프런 워밍업 클럽 3기] CS - 3주차 미션 (자료구조와 알고리즘)

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

버블 정렬

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

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

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

선택 정렬

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

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

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

삽입 정렬

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

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

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

병합 정렬

• 시간 복잡도 : $O(nlogn)$

• 장점 : 위 알고리즘들 보다 성능이 좋다.

• 단점 : 재귀적인 기법으로 이해하기가 어렵고, 구현도 어려움

퀵 정렬

• 시간 복잡도

  • 평균 : $\Theta(nlogn)$

  • 최악 : $O(n^2)$

대부분의 경우 피벗을 중간값으로 설정하므로 배열을 매번 반으로 가를 수 있으므로 평균적인 성능을 가진다고 봄

• 장점 : 병합 정렬보다 더 적은 비교와 더 적은 메모리 공간을 차지하므로, 병합 정렬보다 더 좋은 알고리즘으로 평가됨

• 단점 : 재귀적인 기법으로 이해하기가 어렵고, 구현도 어려움

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

타뷸레이션을 선택.

메모이제이션은 재귀를 이용해 문제를 하향식으로 해결하며 복잡한 문제를 쉽게 해결할 수 있음.

메모이제이션은 계산 결과를 저장하는 방식으로 단점을 해결하는데, 이때 메모리를 이용해 성능을 향상시킴

그러므로, 메모리가 부족한 시스템에서는 메모이제이션을 사용하는것은 오버플로우가 발생할 수 있을것으로 예상됨.

즉, 상향식 접근인 타뷸레이션을 선택하여 메모리를 절약하고, 속도도 빠르게 해결하는 것이 좋아보임.