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

자료구조와 알고리즘

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

버블정렬

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

• 단점 : 성능이 좋지 않음

• 시간 복잡도 : O(n²)

선택정렬

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

• 단점 : 성능이 좋지 않음

• 시간 복잡도 : O(n²)

삽입정렬

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

• 단점 : 성능이 좋지 않음

• 시간 복잡도 : O(n²)

병합정렬

• 장점 : 성능이 좋음

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

• 시간 복잡도 : O(n log n)

   

  퀵정렬

• 장점 : 속도가 빠름

• 단점 : 최악의 경우 시간 복잡도가 O(n²)으로 증가

• 시간 복잡도 : 평균 Θ(n log n), 최악 O(n²)

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

메모리가 부족한 시스템에서는 타뷸레이션이 적합한 것 같습니다. 타뷸레이션은 반복문을 통해 문제를 해결하기 때문에 메모리 사용량이 적습니다. 반면, 메모이제이션은 이미 계산한 결과를 저장해 중복 계산을 피할 수 있지만, 메모리를 많이 사용하므로 적합하지 않습니다.