자료구조와 알고리즘

1. 5가지 정렬 알고리즘 비교

정렬 알고리즘

시간 복잡도 (최선/평균/최악)

장점

단점

버블 정렬

O(n) / O(n²) / O(n²)

구현이 쉬움

성능이 매우 낮음

선택 정렬

O(n²) / O(n²) / O(n²)

교환 횟수가 적음

속도가 느림

삽입 정렬

O(n) / O(n²) / O(n²)

거의 정렬된 데이터에서 빠름

역순 데이터에서 느림

퀵 정렬

O(n log n) / O(n log n) / O(n²)

평균적으로 빠름

최악의 경우 성능 저하 (피벗 선택에 따라)

병합 정렬

O(n log n) / O(n log n) / O(n log n)

안정적인 정렬

추가 메모리 사용 필요

2. 메모이제이션 vs. 타뷸레이션 선택

• 메모리가 부족한 경우 → 타뷸레이션(반복문 방식) 선택

• 이유:

• 메모이제이션(Top-Down, 재귀 방식)은 호출 스택이 깊어지면 스택 오버플로우(Stack Overflow)가 발생할 수 있음.

• 타뷸레이션(Bottom-Up, 반복문 방식)은 스택을 사용하지 않고, 테이블을 채우는 방식이므로 메모리 사용이 더 효율적임.