[CS/자료구조와 알고리즘] 알고리즘 개념

1.정렬(Sort)

:데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것

 

1.1.버블 정렬(Bubble Sort)

:두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

 

1.2.선택정렬(Selection Sort)

①주어진 데이터 중 최소값을 찾는다.

②해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다.

③맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.

 

1.3.삽입정렬(Insertion Sort)

①두 번째 인덱스부터 시작

②해당 인덱스(key값) 앞에 있는 데이터(B)부터 비교해서 key값이 더 작으면, B값을 뒤 인덱스로 복사

③이를 key값이 더 큰 데이터를 만날 때 까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key값을 이동

 

 

1.4.병합정렬(Merge Sort)

:하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법.

 

병합정렬 진행과정

병합정렬의 분할과 동합

 

 

1.5.퀵정렬(Quick Sort)

:기준점(Pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽에 모으는 정렬이다.

 

퀵정렬 설명

 

1.6.탐색 알고리즘

1.6.1.순차 탐색(Sequential Search)

:데이터가 담겨있는 배열을 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법. 데이터를 정렬할 필요가 없으므로 정리되어있지 않은 데이터를 탐색할 때 사용한다. 

 

 

 

 

1.6.2.이진탐색(Binary Search)

: 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법. 데이터가 정렬되어있어야 한다. 이진탐색은 찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교(찾으려는 데이터가 중간점 보다 작으면 왼쪽에서 크면 오른쪽에서 찾는다)하여 원하는 데이터를 찾는 방법이다. 

 

이진탐색과 순차탐색 비교

 

2.그래프(Graph)

2.1.너비 우선 탐색(Breadth-First Search)

:정점의 자식들과 같은 레벨에 있는 노드들(형제 노드)을 먼저 탐색하는 방법.

A - B - C - D - G - H - I - E - F - J

BFS

2.2.깊이 우선 탐색(Depth First Search)

:정점의 자식들을 먼저 탐색하는 방법.

A - B - D - E - F - C - G - H - I - J

 

 

---

참조

• https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

• 패스트캠퍼스 / 한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online.
• https://blog.hexabrain.net/245https://blog.penjee.com/binary-vs-linear-search-animated-gifs/
•