자료구조와 알고리즘

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

• 버블 정렬: 평균적으로 O(n), 최악의 경우 O(n²)
  구현이 간단하지만, 이중 for문으로 인해 성능이 좋지 않다.

• 선택 정렬: O(n²)
  구조가 단순하여 쉽게 구현할 수 있으나, 데이터가 많아질수록 비효율적이다.

• 퀵 정렬: 평균적으로 O(NlogN), 최악의 경우 O(n²)
  병합 정렬보다 비교 횟수가 적고 메모리 사용량도 적지만, 피벗을 잘못 선택하면 성능이 급격히 저하될 수 있다.

• 병합 정렬: O(NlogN)
  분할 정복 알고리즘을 적용하여 안정적인 성능을 보이지만, 구현이 복잡하다.

• 삽입 정렬: O(n²)
  코드가 간단하고 이미 정렬된 데이터에는 효율적이지만, 데이터가 많아지면 성능이 떨어진다.

   

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

타뷸레이션 방식을 사용할 것이다.
이 방법은 계산된 중간 값을 테이블에 저장하며, 일반적인 재귀나 메모이제이션보다 성능이 뛰어나다. 또한, 반복문을 활용해 한 번에 계산을 진행할 수 있어, 메모리가 제한된 환경에서도 효율적으로 사용할 수 있다.