[워밍업 클럽 3기] CS 3주차 - 발자국

삽입 정렬(Insertion Sort)

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

• 장점: 이해 및 구현 간단

• 단점: 성능이 좋지 않음

성능 - O(n^2)

병합 정렬(Merge Sort)

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

• 장점: 성능이 좋음

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

성능 - O(nlogn)

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

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

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

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

퀵 정렬(Quick Sort)

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

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

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

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

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

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

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

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

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

동적 프로그래밍

메모이제이션(memoization)

계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법 → 데이터가 있는지 검색, 없으면 저장

• 하향식 계산 방식

• 재귀적인 기법으로 어려운 문제를 단순히 풀 수 있음

• O(n)의 성능

• 계산 결과를 해시 테이블(key - 계산하는 값, value - 결과 값)에 저장하고 재사용 하기 때문에 속도가 빠름(속도를 위한 메모리 / 캐시 사용)

• 함수 하나를 호출 하는 것 보다 오버헤드가 클 수밖에 없음

타뷸레이션

• 상향식 계산 방식

• 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장