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

   1. 버블 정렬

      1. 앞에 있는 숫자와 옆에 숫자를 비교해서 자리를 바꾸는 알고리즘

      2. 장점

         1. 이해가 쉽고 구현이 간단합니다.

             

      3. 단점

         1. O(n^2) 으로 성능이 좋지 않습니다.

      4. 시간 복잡도

         1. 이중 for문이 핵심 로직으로 O(n^2) 입니다.

   2. 선택 정렬

      1. 정렬된 영역과 정렬되지 않은 영역을 나눠서 정렬되지 않은 영역을 비교하는 알고리즘

      2. 장점

         1. 이해가 쉽고 구현이 간단합니다.

             

      3. 단점

         1. O(n^2) 으로 성능이 좋지 않습니다.

      4. 시간 복잡도

         1. 이중 for문이 핵심 로직으로 O(n^2) 입니다.

   3. 삽입 정렬

      1. 정렬되지 않은 영역에서 데이터(가장 앞에 있는 숫자)를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 "삽입"해서 정렬하는 알고리즘

      2. 장점

         1. 이해가 쉽고 구현이 간단합니다.

             

      3. 단점

         1. O(n^2) 으로 성능이 좋지 않습니다.

      4. 시간 복잡도

         1. 이중 for문이 핵심 로직으로 O(n^2) 입니다.

   4. 병합 정렬

      1. 재귀를 이용해 정렬하는 알고리즘 (분할 정복)

          

      2. 장점

          

         1. O(nlogn) 으로 성능이 좋습니다.

             

      3. 단점

         1. 재귀적인 기법으로 이해하기 어렵습니다.

         2. 구현이 어렵다.

      4. 시간 복잡도

         1. 각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에 logn

         2. 분할된 배열을 병합할 때는 n개의 데이터를 n번 비교

            
            => n, nlogn 곱해서 O(nlogn) 성능이 나옵니다.

   5. 퀵 정렬

      1. 재귀를 이용해 정렬하는 알고리즘 (분할 정복)

      2. 한 번 진행될 때마다 피벗이 정렬되고 정렬된 배열을 좌우로 나눠서 같은 방식으로 재귀 호출을 해 모든 배열을 정렬합니다.

          

      3. 장점

          

         1. O(nlogn) 으로 성능이 좋습니다.

             

      4. 단점

         1. 재귀적인 기법으로 이해하기 어렵습니다.

         2. 구현이 어렵습니다.

      5. 시간 복잡도

         1. 피벗을 기준으로 반을 나눕니다. -> 수가 1개 남을 때까지 반으로 나눕니다. logn

         2. 나눠진 단계를 배열의 원소 수 n만큼 진행

            
            => n, nlogn 곱해서 O(nlogn) 성능이 나온다.

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

• 재귀로 쉽게 구현이 가능하다고 했으니 먼저 메모이제이션을 이용해서 문제를 해결할 거 같습니다.

  • 구현을 하고 실행했을 때 메모리를 어느 만큼 사용하는지 측정해보고 계속 사용할 지 판단하겠습니다.

• 메모제이션으로 구현을 했는데 메모리가 부족하다면 그 때 타뷸레이션을 이용해 문제를 해결하겠습니다.

 ※ 출처

[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 3 (유닛 6~10)]