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

• 버블정렬

서로 인접한 두 요소를 비교하여 정렬하는 알고리즘. 인접한 2개의 요소를 비교해서 교환한다.

일반적으로 데이터의 교환이 이동 작업보다 복잡하다.

시간 복잡도 : O(n^2) 공간 복잡도 : O(1) : 한 개의 임시 변수 필요

안정적 정렬 방식(안정적 정렬이란 중복 된 값을 가진 요소의 순서가 정렬 후에도 유지되는 것을 말한다.)

배열이 거의 정렬 된 상태라면 향상된 버블정렬 알고리즘으로 최선의 시간 복잡도는 O(n)이 된다.

• 선택정렬

   

배열에서 최솟값을 찾아 맨 앞부터 둔다.

일반적으로 데이터의 교환이 이동 작업보다 복잡하다.

시간 복잡도 : O(n^2)

공간 복잡도 : O(1) : 한 개의 임시 변수 필요

서로 떨어져 있는 요소를 교환하기 때문에 안정적 정렬 방식이 아니다.(중복 값이 있을 시 원소의 순서가 바뀜)

• 삽입정렬

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 알고리즘

삽입 하려고 선택한 값을 임시변수에 저장한다.

내부 반복문은 삽입 위치를 찾을 때까지 임시 변수의 값과 비교한다.

삽입 정렬의 시간 복잡도는 O(n^2)로 버블 정렬과 같지만, 실제 성능은 버블 정렬보다 조금 낫다.

카드 게임에서 카드를 배열하는 방법과 비슷하다.

시간 복잡도 : 최악의 경우 -> O(n^2), 최선의 경우 -> O(n)

공간 복잡도 : O(1) : 한 개의 임시 변수 필요

안정적 정렬 방식(안정적 정렬이란 중복 된 값을 가진 요소의 순서가 정렬 후에도 유지되는 것을 말한다.)

위 버블 / 선택 / 삽입 정렬은 이해와 구현이 쉽다는 장점을 가지고 있지만 시간 복잡도가 O(n²)으로 성능이 좋지 않다는 단점을 가지고 있습니다.

퀵정렬

퀵 정렬은 가장 빠른 정렬 알고리즘 중 하나로 널리 사용된다.

그룹을 나누는 기준을 피벗(pivot)이라 한다.

피벗은 마음대로 선택할 수 있으며, 피벗은 어느 그룹에 속해도 상관없다.

퀵정렬은 배열을 나누어 해결하는 과정을 반복하기 때문에 시간 복잡도는 O(n log n)이다.

피벗의 선택에 따라 최악의 경우(예를 들어 1:9)로 나눠지는 경우 시간 복잡도는 O(n^2)이다.

퀵정렬을 피벗을 기준으로 파티션을 나누기 위해 재귀 호출해서 코드를 작성한다.

퀵 정렬/ 병합 정렬은 재귀의 개념을 이용하기 때문에 이해와 구현이 비교적 어렵다는 단점을 가지고 있으나 시간 복잡도가 O(nlogn)으로 성능이 좋다는 장점을 가지고 있습니다.

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

메모이제이션은 순수 함수 호출을 최적화하고 중복 계산을 줄이며 성능을 향상시키는 방법을 제공함으로써 연산 속도는 빠르고 하향식 접근 문제에 대해 빠르게 풀이할 수 있다는 장점이 있지만, 캐시를 유지하면 이전의 모든 입력과 출력을 유지해야 하므로 메모리 사용량도 증가한다. 그러므로 메모리 부족한 시스템에서는 적절치 않다.

타뷸레이션은 문제를 부분 문제로 나눈 다음 작은 문제부터 차례대로 그 결과를 테이블에 저장하는 방식을 말한다. 이렇게 저장된 테이블을 기반으로 큰 문제의 해결을 단계적으로 구축한다.

상향식 계산 방식으로 계산에 필요하지 않을 수도 있는 값도 미리 계산해 테이블에 저장한다. 계산되어 저장된 값을 필요할 때 사용해 빠르게 계산한다.

메모이제이션은 재귀로 쉽게 구현이 가능한 문제에 대해 이점을 가지고 있지만 메모리의 사용이 크다는 단점이 있기 때문에, 결국 메모리가 부족한 시스템에서 적절치 않다고 생각한다.