알고리즘
알고리즘이란? 어떤 문제를 해결하기 위한 여러 동작들의 모임이다.
알고리즘의 주제별 분류
탐색 알고리즘(Searching Algorithm)
- 순서 리스트 또는 비순서화된 리스트에서 어떤 원소의 존재나 위치를 찾는 알고리즘을 말한다.
- 순차 탐색(Sequential Search = Linear Search) : 처음 위치부터 순차적으로 살펴보면서 값이 있는지 보는 단순한 검색 방법이다.
- 이진 탐색(Binary Search) : 정렬되어 있는 리스트에서 중앙 위치로부터 탐색 범위를 반씩 줄이면서 자료를 찾는 방법이다.
정렬 알고리즘(Sorting Algorithm)
- 선택 정렬(Selection Sort) : 매 반복 패스마다 가장 큰/작은 자료를 선택하고 그 반복 패스가 끝나면 이를 선두 위치에 있는 자료와 교환하는 과정을 전체 자료에서 수행한다.
- 버블 정렬(Bubble Sort) : 이웃 요소 간에 대소 비교를 하여 필요시 교환을 수행하며 이 과정을 전체 자료에 걸쳐 수행한다.
- 삽입 정렬(Insertion Sort)
- 퀵 정렬(Quick Sort) : 리스트 안에 임의의 한 요소인 피벗(Pivot)을 선택하여 피봇을 기준으로 작은 요소는 피봇의 왼쪽에 큰 요소는 피봇의 오른쪽으로 옮긴다. 더이상 부분 리스트들이 분할이 불가능할 때까지 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 위와 같은 방식으로 다시 정렬한다.
- 병합 정렬(Merge Sort) : 하나의 리스트를 두 개의 균등한 크기로 분할하고 분한된 부분리스트를 정렬한 다음 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 이때 추가적인 리스트가 필요하고, 실제로 정렬이 이루어지는 시점을 2개의 리스트를 합병하는 단계이다.
그래프 알고리즘(Graph Algorithm)
- 그래프 순회(Graph Traversal)
- 신장 트리 생성 방법
- 최단 경로 알고리즘
해시 알고리즘(Hash Algorithm)
최적화 알고리즘(Optimizing Algorithm)
알고리즘의 설계기법/전략/패러다임에 의한 분류
무작위 대입(Brute and Force)
- 주어진 문제의 모든 가능한 경우를 전부 다 시도해보는 방법이다.
분할 정복(Divide and Conquer) 전략
- 큰 문제를 작은 문제로 분할하여 계산한다.
- 예시 : 이진 탐색, 퀵 정렬, 합벙 정렬
동적계획법(Dynaic Programming) 전략
- 아래에서 위로 해결하면서 전체 문제를 해걸하는 상향식 접근 방식으로 간단한 하위 문제부터 해결하면서 하위 문제의 해를 테이블에 저장해 놓고 좀더 복잡한 상위 문제를 해결해나간다.
- 예시 : 프로이드 최단경로 알고리즘
탐욕 알고리즘(Greedy Algorithm) 전략
- 전체적인 그림을 생각하기보다는 현재 최대의 만족을 추구하는 알고리즘이다. 최적해를 보장하지 않고 차선책을 찾는 알고리즘으로 최적 해를 얻는지 확인하는 절차가 필요하다.
- 예 : 동전 거스름돈을 가장 적은 수의 동전으로 주는 문제, 최소비용 신장 트리 알고리즘(크루스칼 알고리즘, 프림 알고리즘)
백트래킹(Backtracking) 방법
- 문제를 푸는 과정에서 발생할 수 있는 모든 가능한 상태를 트리로 구축하고, DFS를 이용하여 해답을 찾아가는 방법이다.
참고 자료
알고리즘의 정의 - 프로그래밍 입문
알고리즘 분류, 알고리즘 구분 - 정보통신기술용어해설
Algorith Design 알고리즘 설계 - 정보통신기술용어해설
퀵 정렬(quick sort)이란 - heejeong Kwon
합볍 정렬(merge sort)이란 - heejeong Kwon
안녕하세요 코딩을 사랑하는 ssuda 입니다.