정렬 알고리즘
선택정렬
제자리 정렬 알고리즘
과정설명
1. 주어진 배열중에서 최솟값을 찾는다
2. 그값을 맨앞에 위치한 값과 교체한다
3. 맨 처음 위치를 뺀 나머지 리스트를 같은방법으로 교체한다
시간 복잡도: n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸림
거품정렬(버블정렬)
서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지않는다면 자리를 교환하여 정렬하는 알고리즘
시간복잡도 : O(n^2)
삽입정렬
2번째 원소부터 시작하여 그 앞쪽의 원소들과 비교하여 삽입할 위치를 지정한 후 , 원소를 뒤로 옮기고
지정된 자리에 자료를 삽입하여 정렬하는 알고리즘
시간복잡도 : O(n^2)
병합정렬
합병 정렬이라고도 부르며, 분할정복 방법을 통해 구현
분할정복
-> 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식
요쇼를 쪼갠후 다시 합병시키면서 정렬해나가는 방식
쪼개는 방식은 퀵 정렬과 유사
시간복잡도
평균 최선 최악
Θ(nlogn) Ω(nlogn) O(nlogn)
퀵정렬
분할정복 방법을 통해 주어진 배열을 정렬
불안정 정렬에 속한다
1.배열 가운데서 하나의 원소를고른다, 이 원소를 피벗(pivot)이라고 한다.
2. 피벗앞에는 피벗보다 값이 작은 모든 원소들이오고,
피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다, 이렇게 배열을 둘로 나누는것을 분할 이라고 한다. 분할을 마친뒤에는 피벗은
더이상 움직이지 않는다
- 분할된 두개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.
힙정렬
완전 이진트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬 방식
완전이진트리란?=> 삽입할때 왼쪽부터 차례대로 추가하는 이진트리
시간복잡도
평균 최선 최악
Θ(nlogn) Ω(nlogn) O(nlogn)
과정
1.최대 힙을 구성
2.현재 힙 루트는 가장 큰값이 존재, 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임
3. 힙의사이즈가 1보다 크면 위 과정 반복
이분탐색
정렬되어있는 배열에서 데이터를 찾으려 시도할때
탐색 범위를 절반씩 줄여가며 탐색하는 방법
Binary Search는 탐색 대상을 절반씩 계속해서 줄여가기때문에
최악의 경우에도 탐색 횟수가 log2n이 되므로
시간복잡도는 O(logn)
선형탐색보다 훨씬 빠르게 탐색할수있다는 장점
동적 계획법(Dynamic Programming)
하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여
다시 큰 문제를 해결할때 사용하는방법
특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼수있음
사용이유?
일반적인 재귀 방식 또한 DP와 매우 유사하지만
큰 차이점은 일반적인 재귀를 단순히 사용시 동일한 작은 문제들이
여러번 반복되어 비효율적인 계산이 될수있다는것
ex) 피보나치 수열 알고리즘을 구할때
f(n-1)+f(n-2) 함수를 1번씩 호출하면 동일한 값을 2번씩구하게되서
피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가한다
그러나 한번 구한 작은문제의결과값을 저장해두고 재사용하면
계산된 값을 다시 반복할 필요가 없어서
매우 효율적으로 문제를 해결할수있게된다
최단경로
가장짧은 경로를 찾는 알고리즘=> 길찾기 문제로 불림
문제를 그래프로 표현하고 각 지점을 노드,지점간 연결된 도로는 간선이라고 한다
최단경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍이 그대로 적용됨.
다익스트라
그래프에 여러 노드가 있을때 , 특정한 노드에서 출발해서 다른 노드로 가는 각각의 최단 경로를
구해주는 알고리즘
음의간선(0보다 작은 값을 가지는 간선)이없어야 동작.
매번 비용이 적은 노드를 선택해서 임의의과정을 반복하므로, 그리디 알고리즘으로 분류
다익스트라의 원리
1.출발노드를 설정
2.최단 거리 테이블 초기화
3.방문하지않은 노드중에서 최단거리가 가장 짧은 노드 선택
4.해당 노드를 거쳐 다른 노드로 가는 비용계산
5. 위과정에서 3,4번을 반복
최소비용(MST: Minimum Spanning Tree)
신장트리= 스패닝 트리
그래프의 최소 연결 부분 그래프
최소연결= 간선의 수가 가장 적다
n개의 정점을 가지는 그래프의 최소 간선개수는 n-1 이고 n-1개의 간선으로
연결되어 있으면 필연적으로 트리 형태가 된다
그래프에서 일부 간선을 선택해서 만든 트리
-DFS,BFS를 통해 그래프에서 신장트리를 찾을수있다
-하나의 그래프에는 많은 신장트리가 존재할수있다
-신장트리는 특수한 형태이므로 모든 정점들이 연결되어있어야 하고 사이클을 포함해서는 안된다
