알고리즘이란?
알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다.
어떤 일을 수행할 수 있는 일련의 명령어 또는 규칙의 집합이며, 알고리즘 설계하기 위해서는 해야 할 작업을 명확하게 명시해야 하고 문제 해결이나 처리 과정에서의 순서를 단계적으로 서술한다.
어떤 문제를 해결하기 위해 정해진 일련의 절차
- 목록의 내용을 오름차순으로 정렬하려면 어떻게 해야할까?
- 목록에서 특정 단어의 내용이 있는지 찾으려면 어떻게 해야할까?
- 통신에서 주고받는 데이터를 어떻게 압축하고 해제할 수 있을까?
- 암호로 저장된 내용과 입력이 일치하는지 어떻게 확인할 수 있을까?
알고리즘 종류
- 검색 알고리즘
- 정렬 알고리즘
- 수치 알고리즘 - 계산의 해석에서 근사값을 구하기
- 그래프 알고리즘 - 객체관의 관계 모델링
- 문자열 알고리즘
- 암호학적 알고리즘
- 기계학습
- 데이터 압축
정렬 알고리즘
대표적인 정렬 방법 (퀵과 버블)
Quicksort 퀵 정렬
- 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘
- 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
- 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.
-
리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(기준)이라고 한다.
-
피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
-
분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복한다.
참고 : https://www.youtube.com/watch?v=3San3uKKHgg
Bubble Sort 거품 정렬
거품 정렬 또는 버블 정렬(bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다.
상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.
참고 : https://www.youtube.com/watch?v=ebI54DXYQG8
