[워밍업 클럽 3기] CS 3주차 - 자료구조와 알고리즘 미션

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

1) 버블 정렬(Bubble Sort)

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

• 장점: 이해 및 구현 간단

• 단점: 성능이 좋지 않음

성능 - O(n^2)

(n-1) + (n-2) + (n-3) … + 2 + 1 → 등차수열

n(n-1)/2 → (n^2 - n)/2

2) 선택 정렬(Selection Sort)

배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져옴

• 장점: 이해 및 구현 간단

• 단점: 성능이 좋지 않음

성능 - O(n^2)

(n-1) + (n-2) + (n-3) … + 2 + 1 → 등차수열

n(n-1)/2 → (n^2 - n)/2

3) 삽입 정렬(Insertion Sort)

정렬되지 않은 영역의 처음 데이터를 꺼내서, 정렬된 영역 뒤에서 부터 비교하고 적절한 위치에 삽입하여 정렬

• 장점: 이해 및 구현 간단

• 단점: 성능이 좋지 않음

성능 - O(n^2)

4) 병합 정렬(Merge Sort)

배열을 반 씩 분할하고, 가장 작은 단계까지 분할 후 순서에 맞게 병합 - 재귀로 정렬하는 알고리즘

• 장점: 성능이 좋음

• 단점: 이해 및 구현이 어려움

성능 - O(nlogn)

• 하나의 데이터 + 하나의 데이터 → 두 개로 합쳐질 때 비교연산 두 번

• 두 개의 데이터 + 두 개의 데이터 → 네개로 합쳐질 때 비교 네 번

• 각 단계를 거칠 때마다 영역의 수 반으로 줌 → log(n)

• 분할 된 배열을 병합할 때는 n개의 데이터를 n번 비교 → n * logn = O(nlogn)

5) 퀵 정렬(Quick Sort)

분할 정복 알고리즘(재귀 사용)

• 장점: 성능이 좋음 (퀵 > 병합)

• 단점: 이해 및 구현이 어려움

성능 - Θ(nlogn) / O(n^2)

• 데이터가 한 개가 될 때까지 피벗을 기준으로 반을 나눔 → logn

• 나눠진 단계를 배열의 원소수 n 만큼 진행 → n * logn = nlogn

• 피벗이 매번 배열의 반을 가르는 경우 ⇒ Θ(nlogn)

• 최악의 경우는 피벗이 중간이 아닌 한쪽으로 치우친 경우 ⇒ O(n^2)

• 퀵 정렬은 대부분 좋은 피벗을 선택하고 최악의 경우가 발생할 확률이 극히 낮아 평균적인 성능을 말함

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

• 타뷸레이션 이용

• '재귀 호출 + 캐시 저장'으로 스택 메모리 사용하는 메모이제이션과 다르게, 타뷸레이션은 반복문을 이용하여 테이블에 저장하기 때문에 스택 메모리를 사용하지 않음 -> 메모리가 부족한 시스템에선 메모리를 덜 쓰는 타뷸레이션이 적합하다고 생가