[알고리즘] 전공 필기시험 정리

✔️ 정렬 

1. 수행 장소 별 정렬 분류

 

2. 시간 복잡도 별 정렬 분류

O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가)

• 버블 정렬(Bubble Sort)
• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort)

O(n log n)의 시간 복잡도

• 병합 정렬(Merge Sort)
• 퀵 정렬(Quick Sort)

 

3. 정렬 종류

 

1) 버블 정렬(Bubble Sort)

• 인접한 두 수를 비교하며 정렬해나가는 방법으로 O(n²)의 느린 성능
• 앞에서부터 시작하여 큰 수를 뒤로 보내 뒤가 가장 큰 값을 가지도록 완성해나가는 방법 또는 뒤에서부터 반복하여 앞의 작은 값부터 정렬을 완성해나가는 방법

2) 선택 정렬(Selection Sort)

• 한 바퀴 돌 때 가장 작은 값을 찾아 맨 앞과 교환하는 방식의 정렬.
• 앞에서부터 정렬해나가는 특성을 가지고 있음

 

3) 삽입 정렬(Insertion Sort)

• 정렬된 데이터 그룹을 늘려가며 추가되는 데이터는 알맞은 자리에 삽입하는 방식
• 버블 정렬과 선택 정렬과 마찬가지로 최악의 성능인 정렬 알고리즘

 

4) 병합 정렬(Merge Sort)

• 분할 정복과 재귀를 이용한 알고리즘으로 O(n log n)의 시간 복잡도
• 반으로 쪼개고 다시 합치는 과정에서 그룹을 만들어 정렬하게 되며 이 과정에서 2n 개의 공간이 필요
• 합쳐지는 과정

[1,4][2,3] (1과 2 비교) -> 1 선택, 완성된 배열은 [1]

[4][2,3] (4와 2 비교) -> 2 선택, 완성된 배열은 [1,2]

[4][3] (4와 3 비교) -> 3 선택, 완성된 배열은 [1,2,3]

[4][] -> 남는 4 선택, 완성된 배열은 [1,2,3,4]

 

5) 퀵 정렬(Quick Sort)

• 병합 정렬과 마찬가지로 분할 정복 알고리즘
• 추가적인 메모리가 공간이 필요 없음
• 병합 정렬은 균등하게 분할하였다면 퀵 정렬은 Pivot을 설정하고 그 기준으로 정렬
• 다른 정렬 알고리즘보다 빠르며 많은 언어의 정렬 내장 함수로 퀵 정렬을 수행

 

6) 쉘 정렬

• 자기 보다) 작은 수가 나올 때 까지 간격 만큼 우로 밀어 삽입하는 정렬
• 시간복잡도: 평균 O(N^1.5) 최악 O(N^2)
• 안정성 : 없음
• 간격은 Hn = 3 *H(n-1) + 1, n = 데이터 수

1. (자기보다) 왼쪽에 작은 수가 나올 때 까지 간격 만큼 우 로 민다.
2. 왼쪽 간격에 (자기 보다) 작은 수가 나오면 삽입한다.
3. (반복)한다.
4. 간격을 줄인다.
5. 1번 부터 (반복)한다. (삽입정렬과 같으나 간격만큼 우로 민다.)

7) 분포수세기 정렬

• 정의 : 빈도를 누적분포로 저장하고 인덱스로 읽어 삽입(하는 정렬)
• 시간복잡도 : O(N)
• 안정성 : 일반적으로 있음

1. 값의 빈도를 누적분포로 저장한다.
2. 배열을 뒤에서 부터 읽는다.
3. 새로운 배열에 빈도를 인덱스로 읽어 삽입한다.
4. 빈도 수를 감소시킨다.
5. 2번 부터 (반복)한다.

 

8) 힙 정렬

• 우선순위 큐를 이용, 다운 힙, 업 힙 연산으로 정렬
• 시간복잡도 : O(NLogN)
• 안정성 : 동일한 값에 대한 기준이 별도로 있어야 한다. 또는 동일한 값의 존재를 부정

 

9) 기수 교환 정렬

• 값을 비트로, 0과 1로 비교 교환 하는 유사 퀵 정렬
• 시간복잡도 : O(NLogN)
• 안정성 : 동일한 값에 대한 기준이 별도로 있어야 한다. 또는 동일한 값의 존재를 부정한다.
• 제한 : 값 들이 동일한 비트 수를 가져야 한다.

 

 

---

 

✔️ MST 알고리즘 

1. MST Krusukal Algorithm

• 가장 먼저 간선들을 가중치를 기준으로 오름차순 정렬한다
• 루프 도중에 사이클을 만들지 않을 경우에만 간선을 추가한다
• 간선들의 가중치가 동일한 것이 여러개 있을 경우 결과가 달라질 수 있다.
• N개의 노드에 대해 N-1개 간선이 연결되면 종료한다.
• MST : 최소신장트리(모든 정점을 한번씩 방문)