[컴퓨터개론] 알고리즘

알고리즘(Algorithm)

: 제한된 공간과 시간 안에서 데이터를 어떻게 처리할 것인지를 정해 놓은 로직(주어진 인풋으로 정의된 계산을 수행한 뒤 아웃풋을 내는 것을 말함)

 

알고리즘의 종류

탐색(Search)

선형 탐색(Linear Search)

- 맨 앞이나, 맨 뒤부터 순서대로 하나하나 찾아보는 알고리즘이다.

- 가장 단순하고 간단한 탐색 알고리즘이다.

 

1. 맨 끝부터 하나하나 원하는 값을 찾아본다.

2. 원하는 값을 찾으면, 탐색을 종료한다.

 

이분(이진) 탐색(Binary Search)

중간지점을 기준으로 데이터를 반씩 나눠서 탐색하는 알고리즘이다.

 

1. 중간지점을 선택한 뒤, 중간 지점을 기준으로 죈쪽 혹은 오른쪽 부분만 남긴다.

2. 남긴 부분 중에서 다시 중간 기점을 선택한 뒤, 횐쪽 혹은 오른쪽만 남긴다.

3. 위 과정을 원하는 값을 찾을 때 까지 반복한다.

 

순차 탐색(Sequential Search)

데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘입니다. 이 순차 탐색은 데이터를 따로 조작할 필요가 없어 단순하지만 비효율적이라는 단점을 지니고 있습니다. 

 

해시 탐색(Hash Search)

선형 탐색이나 이진 탐색은, 어떤 값이 어떤 index에 들어있는지에 대한 정보가 없는 상태에서 탐색할 때 사용하는 방식이었다.

반면에 해시 탐색은 값과 index를 미리 연결해 둠으로써 짧은 시간에 탐색할 수 있는 알고리즘이다.

 

함수를 사용하여 데이터를 보관한 후에 보관하는데 사용된 함수를 사용하여 한 번에 데이터를 탐색한다.

---

정렬(Sorting)

버블 정렬(Bubble Sort)

버블 정렬은 첫번째 원소부터 인접한 원소와 비교하며 자리를 바꾸면서 맨 끝부터 정렬하는 방식이다. i 번째 원소와 i + 1 번째 원소의 값을 비교하고 만약 i번째의 값이 i + 1 번째의 값보다 크다면 둘의 자리를 바꾸어 값이 큰 원소가 뒤에 위치하게 한다. 이를 반복해서 수행하면 가장 큰 값부터 뒤쪽에 쌓이게 된다. 즉 가장 큰 값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬한다. 버블 정렬은 정렬 방식이 마치 물속에서 올라오는 물방울과 같다고 하여 버블 정렬이라는 이름이 붙여졌다.

 

장점

- 구현이 간단하다

- 데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.

 

단점

- 데이터를 하나씩 비교하기 때문에 비교 횟수가 많아지므로 시간이 오래 걸린다.

 

선택 정렬(Selection Sort)

과정

1) 주어진 배열 중에서 최솟값을 찾는다.

2) 그 값을 맨 앞에 위치한 값과 교체한다.

3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

4) 하나의 원소만 남을때까지 위의 1~3 과정을 반복한다.

 

장점

- 자료 이동 횟수가 미리 결정된다.

 

단점

- 안정성을 만족하지 않는다.

- 즉, 값이 같은 레코드가 있을 경우에 상대적인 위치가 변경될 수 있다.

 

삽입 정렬(Insertion Sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

 

장점

- 안정한 정렬 방법

- 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.

- 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

 

단점

- 비교적 많은 레코드들의 이동을 포함한다.

- 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

퀵 정렬(Quick Sort)

1) 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.

2) 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽 피벗보다 큰 요소들)

3) 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.

- 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다.

- 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.

4) 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

- 리스트의 크기가 0이나 1이 될 때까지 반복한다.

 

장점

- 속도가 빠르다 : 시간 복잡도가 O를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.

- 추가 메모리 공간을 필요로 하지 않는다 : 퀵 정렬은 O만큼의 메모리를 필요로 한다.

 

단점

- 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

 

특징

- 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.

ex) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값을 피벗으로 선택한다.

 

병합 정렬(Merge Sort)

과정

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

 

합병 정렬은 다음의 단계들로 이루어진다.

- 분할 : 입력 배열은 같은 크기의 2개의 부분 배열로 분할한다.

- 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.

- 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

합병 정렬의 과정

- 추가적인 리스트가 필요하다

- 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.

- 합병 정렬에서 실제로 정렬이 이루어진 시점은 2개의 리스트를 합병하는 단계이다.

 

단점

- 만약 레코드를 배열로 구성하면, 임시 배열이 필요하다

- 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

 

장점

- 안정적인 정렬 방법 : 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.

 

힙 정렬(Heap Sort)

- 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법

- 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

과정

1) 정렬해야 할 n 개의 요소들로 최대 힙(완전 이진 트리 형태)를 만든다.

2) 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.

3) 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

 

장점

- 시간 복잡도가 좋은 편

- 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 이다.

 

기수 정렬(Radix Sort)

기수정렬은 낮은 자리수부터 기뵤하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다.

기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다.

 

과정

1) 0 ~ 9까지의 Bucket(Queue 자료구조)을 준비한다.

2) 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다.

3) 0부터 차례대로 버킷에서 데이터를 다시 가져온다.

4) 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다.

아래의 8개 데이터에 대해 기수 정렬을 해보면,

먼저 1의 자리 숫자부터 시도를 합니다. 데이터 순서대로 각 1의 자리에 해당되는 Queue에 데이터가 들어가게 됩니다. 15 같은 경우는 1의 자리가 5 이므로 Queue 5에 들어가는 방식입니다.

위의 그림처럼 다시 0번 Queue부터 차례대로 데이터를 가지고 와서 원래의 배열에 넣어주게 됩니다.

1의 자리에 대한 정렬이 완료되었습니다. 다음으로는 10의 자리에 대하여 같은 작업을 반복합니다.

마찬가지로 각 데이터의 10의 자리에 해당되는 Queue에 데이터를 위치 시킵니다. 그런 다음 0번 Queue부터 차례대로 다시 데이터를 가지고 옵니다.

특징

- 시간 복잡도는 O(dn)

- 자리수가 고정되어 있어서 안정성이 있는 정렬 방식

 

 

 

 

 

 

참고 : https://lktprogrammer.tistory.com/48

참고 : https://gmlwjd9405.github.io/

참고 : https://jbhs7014.tistory.com/180

참고 : https://bba-dda.tistory.com/21