1. 시간 복잡도
시간 복잡도란, "입력값의 변화에 따라, 연산 횟수에 비해 시간이 얼마나 걸리는지 알려주는 지표"이다. 즉, 효율적인 알고리즘인지 판단하기 위해 수행 시간을 측정하는 것이다.
1) 빅 오
- WORST일 때 실행 시간 → 주로 사용한다.
2) 빅 오메가
- BEST일 때 실행 시간
3) 빅 세타
- 평균 실행 시간 (빅오, 빅오메가의 접점)
⭐ 특징
- 항상 최고차항만 표기한다. (상수 및 계수는 무시한다.)
- for문이 중첩된 갯수로 파악할 수 있다.
+(추가) 공간복잡도 → '메모리 사용량'으로, 현대의 기술 발전으로 저장 용량에 대한 걱정은 줄어듦 (따라서 시간 복잡도가 더 중요해졌다.)
2. 정렬 알고리즘 1 (버블/삽입/선택)
1) 버블 정렬
- 인접한 두 원소를 비교해서 정렬하는 알고리즘
void bubble_sort(int arr[], int n){
for(int i=n-1; i>0; i--){
for(int j=0; j <i; j++){
if(arr[j]<arr[j+1]){
temp = arr[i];
arr[j] = arr[j+1];
arr[j+1] = temp;
}..2) 삽입 정렬
- 앞에서부터 차례대로 이미 정렬된 부분과 비교해 자신의 위치 부분에 삽입하는 정렬
void insertion_sort(int arr[], int n){
int j=0;
for(int i=1; i<n; i++){
key = arr[i];
for(j=i-1; j>0 && arr[j]>key; j--){
arr[j+1] = arr[j];
}
arr[j+1] = key;
}..3) 선택 정렬
- 해당 순서의 위치에 넣을 원소를 가장 작은 값을 선택하는 방식의 정렬
void selection_sort(int arr[], int n){
int min;
for(int i=0; i<n-1; i++)P
min = i;
for(int j=i+1; j<n; j++){
if(arr[j] < arr[min]
min = j;
}
if(i!=min){
int temp = arr[i];
arr[i] = arr[min]
arr[min] = temp;
}..3. 정렬 알고리즘 2 (병합/퀵)
1) 병합 정렬
- 분할정복 알고리즘을 적용한 정렬 방법
분할정복 : Divide-Merge-Base_case 3가지 과정을 거쳐 풀어내는 과정
2) 퀵 정렬
- 피벗값을 통한 분할정복 알고리즘 적용 정렬 방법
- 병합 정렬에 비해, 매우 빠른 수행 속도로 실행된다.
⭐ 정렬 알고리즘의 시간복잡도&공간복잡도
-
선택/버블/삽입 정렬
-
병합 정렬
-
퀵 정렬
4. 배열, 동적배열
1) 배열
- linear(선형) 자료구조
- 인덱스를 통한 빠른 조회가 가능하다는 장점이 있으나,
- 처음부터 크기가 고정되어, 메모리 낭비 혹은 overhead(메모리 초과)가 발생할 수 있다는 단점이 있다.
2) 동적 배열
- 배열의 장점을 그대로 가져오면서, 단점을 보완한 자료구조
- resize를 통해 유동적으로 메모리 저장 공간을 늘린다.
💡점검하기
-
시간 복잡도는 뭔가요?
: 해당 알고리즘이 수행되는데 걸리는 시간이다. -
퀵정렬, 병합정렬 비교해서 설명해주세요
: -
선택정렬은 뭔가요?
: 가장 작은 값을 찾아내어 순서대로 정렬하는 알고리즘이다. -
본인이 알고있는 정렬 알고리즘 중에 제일 빠른 정렬 알고리즘은 무엇인가요? - 시간복잡도 측면에서 말하기
: 퀵 정렬로, 음..O(n)시간..? -
퀵 정렬이 제일 빠르다면, 항상 빠르다고 할 수 있을까요?
: 상황에 따라 다르다고 했다. -
버블정렬 수도코드로 구현해주세요
-
삽입정렬을 수도코드로 구현해주세요
-
퀵 정렬을 수도코드로 구현해주세요
-
Array는 어떤 자료구조인가?
: 선형적 자료구조로, 인덱스를 통한 빠른 조회가 장점이나, 고정된 메모리 크기로 낭비 혹은 오버헤드가 발생한다는 단점을 가진다. -
Array의 단점은 무엇인가요? 그걸 극복하기 위한 해결책이 무엇일까요?
: 앞서 말한 대로, fixed-size memory이다. 이를 보완한 것이 동적 배열, 즉 dynamic array이다.
