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

자료구조

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

   버블 정렬
   - 특징: 인접한 두 요소를 비교해서 큰 값을 뒤로 보내는 방식

    
   - 시간복잡도: 최선: O(n) / 평균,최악: O(n²)

    
   - 장점: 구현이 아주 간단하고 직관적임

    
   - 단점: 성능이 너무 안 좋음, 실전에서 거의 사용 하지 않음

   
   

   선택 정렬

   
   - 특징: 가장 작은 값을 찾아서 앞으로 하나씩 정렬해가는 방식

    

    
   - 시간복잡도: 최선,평균,최악: O(n²)
   - 장점: 구현 쉬움, 자리 바꿈(Swap) 횟수가 적음
   -

   단점: 효율성 낮음, 데이터 크기 커지면 성능이 떨어짐
   

   삽입 정렬
   - 특징: 정렬된 부분에 새 값을 '삽입'하는 방식
   - 시간복잡도: 최선: O(n) / 평균,최악: O(n²)
   - 장점: 거의 정렬된 상태일 땐 빠름, 구현 쉽고 안정 정렬
   - 단점: 역순으로 정렬되어 있을 경우 성능이 크게 하락
   

   병합 정렬
   - 특징: 분할 → 정렬 → 병합하는 재귀 방식 (Divide & Conquer)
   - 시간복잡도: 항상 O(nlogn)
   - 장점: 성능이 좋음. 큰 데이터에도 효율적, 정렬 정확도 높음
   - 단점: 이해와 구현이 어려움. 메모리 공간을 많이 차지

   
   

   퀵 정렬
   - 특징: 분할 → 정렬 → 병합하는 재귀 방식 (Divide & Conquer)
   - 시간복잡도: 항상 O(nlogn)
   - 장점: 성능이 좋음. 큰 데이터에도 효율적, 정렬 정확도 높음

   
   - 단점: 이해와 구현이 어려움. 메모리 공간을 많이 차지

    

    

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

    

   지금 당장으로서는 타뷸레이션을 사용할 것 같습니다. 일단 재귀의 경우, 하위 단계의 결과값을 상위 단계에서 사용할 수 있을 지를 판단해야 하는데 일단 여기서부터 재귀로 풀어야겠다는 생각을 도출하기까지 쉽지 않으며 메모리가 부족한 환경에서 콜 스택이 쌓이는 건 굉장히 치명적입니다. 재귀로 해결해야 한다면 최대 재귀 깊이를 설정하여 콜 스택이 무한정 쌓이지 않도록 방지하는 방법을 사용할 수 있을 것 같습니다.