알고리즘 요약
알고리즘
문제를 해결하기 위한 방법이나 절차
시간/공간 복잡도
알고리즘 성능을 분석하는 지표이며, 주로 시간 복잡도와 공간 복잡도는 반비례하는 성질을 가지고 있다.
시간 복잡도 : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.
버블 정렬 - Bubble Sort
현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다.
- 가장 쉽다.
- 퍼포먼스가 좋지 않아 잘 사용하지 않음
시간 복잡도 : O(n²)
공간 복잡도 : 하나의 배열만 사용하여 정렬하므로 O(n)이다.
선택 정렬 - Selection Sort
전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식이다.
- 전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환한다.
- 그다음 두번쨰로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환한다.
- 이과정을 반복한다.
시간 복잡도 : O(n²)
공간 복잡도 : O(1)
삽입 정렬 - Inserting Sort
정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 삽입하는 방법이다.
- 0번 인덱스는 건너뛴다.
- 0~1번 인덱스 중 1번 인덱스 값이 들어가야할 위치를 찾아서 넣는다
- 0~2번 인덱스 중 2번 인덱스 값이 들어가야할 위치를 찾아서 넣는다
- 0~n번 인덱스 중 n번 인덱스 값이 들어가야할 위치를 찾아서 넣는다.
시간 복잡도 : O(n²)
공간 복잡도 : O(n)
병합 정렬 - Merge Sort
n개의 원소를 가지고 있는 배열을 2로 나누어지지 않을 때까지 분할 후, 임시 배열에 나누어진 원소를 비교하여 담은 후, 정렬된 임시배열을 원래 배열에 다시 대입함으로서 정렬하는 방법이다.
분할정복 - Divide and Conquer- 최선, 최악, 최선이 모두
O(n log n)시간 복잡도를 가진다. - stable하다
시간 복잡도 : O(n log n)
공간 복잡도 : O(n)
퀵 정렬 - Quick Sort
피봇 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다.
- 가장 높은 인덱스의 값을 피벗으로 지정하고
- 가장 낮은 인덱스부터 증가하여 피벗보다 큰 수의 인덱스와 가장 큰 인덱스부터 증가한다.
- 피벗보다 작은 수의 인덱스를 구한 후 작은 인덱스와 큰 인덱스 숫자를 스왑 후
- 다음 작은 인덱스의 숫자를 다음 피벗으로 지정한다.
분할정복 - Divide and Conquer- unstable하다
시간 복잡도 : O(n log n) 최악: O(n²)
공간 복잡도 : O(n)
기수 정렬
낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다.
- 0~9 까지의 Queue 자료구조의 Bucket을 준비한다.
- 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다.
- 0부터 차례대로 버킷에서 데이터를 다시 가져온다.
- 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다.
- 비교연산을 하지 않는다.
- 문자열과 정수 정렬만 가능하다.
- 자리수가 정해진 경우 빠르다
- 시간복잡도 : O(kn)
k는 자리수, n은 데이터 수
알고리즘 예상 질문
54321 배열이 있을 때(역순정렬 시)), 어떤 정렬을 사용하면 좋을까요?
선택정렬 입니다. 선택정렬은 앞에 저장되어야 하는 수를 선택하여 앞자리와 교환하여 정렬합니다.
반복은 최대 원소의 개수의 반만큼 O(N/2)일어나게 됩니다.