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

버블정렬,선택정렬,삽입정렬,병합정렬,퀵정렬이 있습니다..

버블정렬

성능 : O(n²)의 성능을 가집니다

장점 : 구현이 쉽고 단순합니다.

단점 : 성능이 좋지않아 대규모 데이터 처리에 좋지않습니다.

선택정렬

성능 : O(n²)의 성능을 가집니다

장점 : 구현이 쉽고 단순합니다. (버블정렬과 동일)

단점 : 성능이 좋지않아 대규모 데이터 처리에 좋지않습니다. (버블정렬과 동일)

삽입정렬

성능 : O(n²)의 성능을 가집니다

장점 : 구현이 쉽고 단순합니다. (버블정렬과 동일)

단점 : 성능이 좋지않아 대규모 데이터 처리에 좋지않습니다. (버블정렬과 동일)

병합정렬

성능 : O(n log n)의 성능을 가집니다.

장점 : 안정적인 성능을 보여줌

단점 : 구현과 이해가 어렵고 메모리 공간을 많이 차지

퀵정렬

성능 : 평균적으로 O(n log n)의 성능을 가지고 최악의 경우 피벗이 한쪽으로 치우쳐 O(n²)를 가지지만 보통 최악의경우가 나올 확률은 극히 낮아 좋은 피벗을 선택해 평균적인 성능으로 말해 O(n log n)의 성능을 가집니다.

장점 : 속도가 빠르고 추가 메모리 사용이 거의 없음

단점 : 최악의 경우 O(n²)의 성능을 가짐

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

재귀로 쉽게 구현할 수 있는 문제라면 메모이제이션을 사용하는 것이 좋습니다

메모이제이션은 재귀 기반 방식이라 코드가 직관적이고 분할하여 해결하기도 쉬워 구현이 간단합니다.
반면 타뷸레이션은 반복문 기반으로 계산을 순서대로 처리해 안정적이지만 코드가 길어질 수 있습니다.

타뷸레이션과 메모이제이션을 실행했을때

   public static int fibonacci1(int n){ // 타뷸레이션
        if(n <= 1){
            return n;
        }
        int[] table = new int[n+1];
        table[0] = 0;
        table[1] = 1;
        for(int i = 2;i <= n;i++){
            table[i] = table[i - 2] + table[i - 1];
        }
        return table[n];
    }

    public static int fibonacci2(int n,HashMap<Integer,Integer> memo){ // 메모이제이션
        if(n == 0 || n == 1){
            return n;
        }
        if (!memo.containsKey(n)) {
            memo.put(n, fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo));
        }
        return memo.get(n);
    }



    public static void main(String[] args) {
        HashMap<Integer,Integer> memo = new HashMap<>();
        System.out.println("메모이제이션 : " + fibonacci2(5,memo));
        System.out.println("타뷸레이션 : " + fibonacci1(5));
    }