Computer Science
[CS] 알고리즘
cheery7272
2022. 12. 30. 16:40
선택 정렬
- 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾼다.
- O(N^2)의 시간 복잡도를 가진다.
삽입 정렬
- 특정한 데이터를 적절한 위치에 삽입한다는 의미로 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
- 두번째 데이터부터 시작한다. 왜냐하면 첫번째는 정렬되어 있다고 판단하고 시작하기 때문
- 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다.
- 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.
- O(N^2)의 시간 복잡도를 가진다.
- 거의 정렬된 상태라면 최선의 경우 O(N)의 시간 복잡도를 가진다.
퀵 정렬
- 대부분 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
- 기준을 성정한 후 큰수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작
- 교환하기 위한 기준을 피벗이라 한다.
- 호어 분할 방식의 피벗 설정은 리스트에서 첫번째 데이터를 피벗으로 정한다.
- 현재 리스트의 데이터 개수가 1개인 경우에 이미 정렬이 완료되었다고 간주한다.
- 어느정도 정렬되어 있는 경우에는 매우 느리게 동작한다.
- 데이터의 특성을 파악하기 어렵다면 계수정렬보다 퀵정렬을 사용하는게 적합.
- O(NlogN)의 시간 복잡도를 가진다.
계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 사용할 수 있다.
- 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다.
- 리스트에 데이터의 횟수를 저장하여 리스트를 출력
- 데이터의 개수 N, 데이터 중 최대값 K일때, 최악의 경우 O(N+K)를 보장
- 공간복잡도 O(N+K)
사용 적합
- 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
- 동일한 값을 가지는 데이터가 여러개 등장할때 적합하다.
- ex) 성적이 100점을 맞은 학생이 여러 명일 경우 효과적
- 데이터의 크기가 한정되어 있고 데이터의 크기가 많이 중복되어 있을수록 유리하다.
- 왠만해선 기본 정렬 라이브러리를 사용하고 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 경우는 계수정렬을 사용하면된다.
사용 부적합
- 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 사용할 수 없다.
- 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 사용하기 어렵다.
모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000일 경우 총 1,000,001개의 데이터가 들어 갈 수 있는 리스트를 초기화 해야 한다.
파이썬의 기본 정렬 라이브러리는 O(NlogN)을 보장하며 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 기반으로 만들어졌다.
이진탐색
- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
- 시작점,끝점, 중간점 변수 3개를 사용한다.
- 데이터의 개수가 1000만개 이상일 경우에 이진 탐색을 의심해보자!
파라메트릭 서치
- 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제에서 이진탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
다이나믹 프로그래밍
- 메모리 공간을 더 사용하면서 연산 속도를 비약적으로 증가시킬 수 있는 방법
- 큰 문제를 작게 나누고 같은 문제라면 한번씩만 풀어 문제를 해결하는 방법
사용 조건
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모이제이션
- 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
- 이전에 계산된 결과를 일시적으로 기록해 놓는 개념
탑 다운 방식
- 큰 문제를 해결하기 위해서 작은 문제를 호출
보텀업 방식
- 작은 문제부터 시작하여 큰 문제를 해결
다익스트라 알고리즘
- 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘
- 음의 간선이 없을떄 동작한다.
- O(ElogV)를 보장한다.
다익스트라 구현
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 3,4과정을 반복한다.
플로이드 워셜
- 모든지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
서로소 집합 자료구조
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- union-find로 해결
union
- 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
find
- 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
신장 트리
- 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 존재하이 않는 부분 그래프
크루스칼 알고리즘
- 가장 거리가 짧은 간선부터 차례대로 집합에 추가한다.
- O(ElogE)의 시간 복잡도를 가진다.
위상정렬
- 순서가 정해져 있는 일련의 작업을 차례대로 수행할때 사용하는 알고리즘
- 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는것
- 싸이클이 발생하지 않는다.
- O(V+E)의 시간복잡도를 가진다.