[탑기공] 정렬, 검색, 그래프 탐색 알고리즘

 

---

멘토링

 

ⓛ 정렬 알고리즘은 종류별 동작방식 중심으로 학습을 권고합니다.
- 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬 등

② 검색 알고리즘은 분류 및 
제어 검색에서 피보나치 탐색과 이진트리 탐색 중심으로 학습을 권고합니다.

③ 그래프 탐색 알고리즘은 DFS, BFS의 동작 방식 및
Psuedo Code를 작성하는 수준까지 학습하길 권고합니다.

 

정렬 알고리즘 개념

 

원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘

 

정렬의 분류

 

정렬 장소에 따라 내부정렬(Internal Sort)과 외부정렬(External Sort)로 분류

 

내부정렬

 

소량의 데이터에 대해 주기억 장치에 올려서 정렬하는 방식으로
정렬 속도는 빠르나 주기억 장치의 용량에 의해 정렬할 수 있는 데이터의 양이 제한됨

 

외부정렬

 

대량의 데이터에 대해 보조 기억 장치에서 정렬하는 방식으로
대량의 데이터를 몇 개의 서브 파일로 나누어 내부 정렬을 한 후
보조 기억 장치에서 정렬된 각 서브 파일들을 병합하는 방식으로 속도가 느림

 

정렬 알고리즘 종류

헷갈리는 두 개의 내부 정렬 알고리즘의 동작방식을 암기하기 위한 저만의 방식입니다.

[두음] 선말삽초

선택 정렬 - 뒤쪽에 있는 것 바꾸기, 끝 말(末)
 - 오름차순 정렬 기준, 최댓값을 찾아서 미정렬된 마지막 값과 변경
 - 처음엔 n 위치와 다음에 n-1 위치 ...

삽입 정렬 - 앞쪽에 있는 것 바꾸기, 시작 초(初)
 - 데이터가 정렬되어 있다고 가정하고, 앞에 있는 데이터 비교하여 적절한 위치에 삽입

 

내부 정렬 알고리즘의 분류

 

<출처 : 탑싯 에센스>

[두음] 삽교선병분

삽입법, 교환법, 선택법, 병합법, 분배법

 

내부 정렬 알고리즘의 수행시간 비교

 

<출처: 탑싯 에센스>

삽입, 선택, 퀵 정렬의 최악 수행 시간은 O(n^2)
힙(heap), 머지(merge) 정렬의 최악 수행 시간은 O(nlogn)

힙 정렬과 머지 정렬이 삽입, 선택, 퀵 정렬 대비 수행시간이 빠를 수밖에 없는 이유를
개념적으로 이해하시길 바랍니다.

선택 정렬 동작 방식

 

<출처: 탑싯 에센스>

 

최솟값을 찾아 왼쪽으로 이동시키는데 데이터의 크기(개수)만큼 반복하여 정렬하는 방법
→ 최댓값을 찾아 오른쪽으로 이동시키는데 데이터의 크기(개수)만큼 반복하여 정렬하는 방법

오름차순 정렬 기준 배열에서 최댓값을 찾아
오른쪽으로 이동하기 위해 배열의 맨 마지막 값 자리와 바꾼다.

다시 최댓값을 찾아
배열의 맨 마지막 값 - 1 자리와 바꾼다.

반복

최악 수행 시간 O(n^2)

삽입 정렬 동자 방식

 

데이터가 정렬되어 있다고 가정하고 값을 해당 위치에 삽입하여 정렬하는 방법

앞에 데이터들은 이미 정렬되었다 가정하고 
이미 정렬된 데이터들 사이에 적절한 위치에 삽입하는 방식

(5) 6 10 4

(5) (6) 10 4

(5) (6) (10) 4

--------------
(5) (6) 4 (10)
(5) 4 (6) (10)

(4) (5) (6) (10)

버블 정렬 동작 방식

 

인접한 데이터 간에 교환이 계속해서 일어나면서 정렬이 이루어지는 방법

 

<출처: 탑싯 에센스>

 

퀵 정렬 동작 방식 이해 위한 주요 키워드

 

분할 정복, 피봇, Low / High, 재귀 호출

분할 정복(Divide and Conquer)의 방식으로 고안된 정렬 방법으로
먼저 임의의 기준을 선택하여 그 기준보다 작은 값을 왼쪽에,
큰 값을 오른쪽에 위치시킨 후
다시 임의의 기준을 선택하여 왼쪽과 오른쪽을 반복하여 나누어 가며 정렬하는 방법

 

검색 알고리즘의 개념

 

데이터 집합에서 원하는 항목을 효율적으로 찾는 기법

 

검색 알고리즘 분류

 

[두음] 선제함

선형 검색, 제어 검색, 특수 함수를 이용하여 접근하는 방식(해싱)

 

<출처: 탑싯 에센스>

제어 검색에서 파보나치 탐색, 이진 트리 탐색(BTS)는 주의 깊게 학습하시길 권고합니다.

 

그래프 탐색 알고리즘

 

그래프 탐색 방법에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 방법이 있다.

 

깊이 우선 탐색 (DFS, Depth First Search)

 

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 데까지 깊이 탐색해가다 
더 이상 갈 곳이 없으면 마지막 갈림길 간선이 있는 정점으로 되돌아와 
다른 방향의 간선으로 탐색을 계속 반복하여
목표 노드를 찾을 때까지 정점을 방문하는 방법

후입선출 구조의 스택을 사용, 재귀함수로도 구현 가능하며 
방문 처리하는 visited 함수 일반적 사용

 

너비 우선 탐색 (BFS, Breadth First Search)

 

하나의 시작 정점을 반문한 후 인접한 노드를 먼저 탐색하는 방법으로
시작 정점으로부터 가까운 정점을 먼저 방문하고
멀리 떨어져 있는 정점을 나중에 방문하는 탐색 방법
큐 사용

 

신장 트리

 

무방향 가중치 그래프 내 모든 정점을 포함하고 서로 연결되어 있는 트리의 특수한 형태로
사이클을 포함해서는 안 되는 트리

 

최소 신장 트리

 

신장 트리를 구성하는 가중치의 합이 최소인 신장 트리
알고리즘: 크루스칼(Kruskal), 프림(Prim) 알고리즘

 

크루스칼 알고리즘

 

정점에 연결된 간선 가운데 가중치가 최소인 간선을 선택하고
추가된 간선이 사이클을 만드는지 체크하는 방식으로 처리

간선의 가중치를 오름차순 정렬 후 Union-Find 알고리즘 적용하여 일반적으로 구현

 

프림 알고리즘

 

분석 대상 그래프에서 임의의 한 정점을 선택하여 
각 반복과정마다 그때까지 구성된 최소 신장 트리 부분에 
방문하지 않은 새로운 정점과 간선을 선택하여 확장해 나가는 방법

---

기출 문제

 

(응용 122-4-2)
정렬 알고리즘은 컴퓨터 분야에서 가장 많이 연구된 분야 중 하나이다.

가. 선택정렬(Selection Sort)과 삽입정렬(Insertion Sort), 퀵정렬(Quick Sort) 알고리즘을 설명하시오.
나. 다음 키 값을 갖는 파일을 퀵정렬(Quick Sort) 알고리즘을 사용하여 오름차순으로 정렬하려고 한다. 
피벗이 50일 때 수행되는 분할과정을 단계적으로 설명하시오.
(단, n=8 : 50, 80, 20, 90, 40, 10, 30, 60)

 

(관리 105-4-6)
Quick Sort 알고리즘에 대하여 설명하고 아래의 C언어 소스 코드에서 필요시 함수등을 추가하여 완성하시오
(단, Sort 순서는 오름차순)

#include

void QuickSort(int *data, int n){
}

void main(){ 
 char data[8] = {'B','I','D','O','Z','L','H'};  
 puts(data);  
 QuickSort(data,7);  
 puts(data);
}

 

(관리 99-4-2)
퀵 정렬(Quick sort) 알고리즘을 설명하고, 
다음 데이터를 퀵 정렬 알고리즘을 사용해서 정렬하는 과정을 설명하시오. 
30,15,16,24,38,33,17,29,32

 

(관리 95-2-6)
다음은 C언어로 작성된 버블정렬(Bubble Sort) 알고리즘 프로그램의 일부이다. 
프로그램을 완성하시오.

#include
int main(){
  int data[5] = {2, 5, 1, 4, 3};
  bubble(data, 5);
  for(int i=0; i<5; i++) {
    print("%d ", data[i]);
  }
    return 0;
}

 

(관리 90-2-4)
정렬(Sorting) 알고리즘의 하나인 삽입정렬(insertion sorting) 알고리즘을 기술하고 
이 알고리즘이 어떤 경우에 효과적인지 설명하시오. 또한 평균 연산시간(Big O)과 
최악의 연산시간을 근거와 함께 설명하시오.

 

(응용 116-4-2)
아래 그래프에서 최소신장트리(MST: Minimum Spanning Tree)를 구하는 과정을 
2개의 알고리즘을 이용하여 설명하시오.

가. 크루스컬(Kruskal) 알고리즘
나. 프림(Prim) 알고리즘

 

(관리 117-3-3)
MST(Minimun Spanning Tree)를 구하는 알고리즘인 
크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘을 설명하시오.

 

(관리 123-4-6)
6. 다음에 대하여 설명하시오.
가. 최단경로 알고리즘의 유형 4가지
나. 다음 그래프에서 4가지 알고리즘 계산방법
- A, B, C, D, E 5개 노드로 구성된 그래프(A가 출발지, E가 목적지임)
다. "나"의 4가지 알고리즘 계산결과 비교

 

(관리 96-1-1)
그래프를 이용하여 최적 경로를 찾는 데 이용되는 
최소 신장 트리(Minimal spanning tree) 알고리즘에 대하여 설명하시오

 

(관리 98-4-1)
인공지능 응용 정보시스템이나 게임 개발 시 길 찾기에 이용되는 
Djkstra 알고리즘과 A* 알고리즘을 비교 설명하시오.

 

(관리 87-1-2)
휴리스틱 알고리즘인 A*에 대해 설명하시오.

 

참고 자료

정렬 알고리즘 - 나무위키 (namu.wiki)

정렬 알고리즘 - 나무위키

선택 정렬

https://swblossom.tistory.com/38

[C/C++] 선택 정렬(selection sort) 알고리즘을 활용한 오름차순정렬

삽입 정렬

https://swblossom.tistory.com/42

[C/C++] 삽입 정렬(insertion sort)

버블 정렬

https://bigdatadiary0819.tistory.com/111

[C++] 버블 정렬(Bubble Sort)

인접행렬과 재귀를 통한 DFS 구현

https://code-lab1.tistory.com/15

[알고리즘] 깊이 우선 탐색, DFS(Depth First Search)알고리즘이란?| C언어 DFS 구현

스택이용 DFS, 큐 이용 BFS 구현

https://sweetday-alice.tistory.com/176

[C++] DFS와 BFS 구현하기

퀵 정렬(quick sort)

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog