5장 요약정리

1. 정렬 알고리즘

① 비교 기반 정렬 알고리즘

 

종류	특징	평균 시간 복잡도
버블 정렬	인접한 두 수를 비교해 정렬	O(n^2)
선택 정렬	정렬되지 않은 배열에서 최솟값을 선택해 정렬
삽입 정렬	정렬된 배열에 탐색 중인 요소 삽입
합병 정렬	분할 정복 기반 알고리즘, 배열을 1 이하 크기로 분할한 후 합병 과정에서 정렬	O(n log n)
퀵 정렬	분할 정복 기반 알고리즘, 피봇을 선택해 피봇보다 작은 수의 배열과 피봇보다 큰 수의 배열로 분할하며 정렬, 피봇에 따라 시간 복잡도가 달라질 수 있음
힙 정렬	힙 기반 정렬 알고리즘, 최대 힙을 이용해 오름차순 정렬 & 최소 힙을 이용해 내림차순 정렬

② 비교 기반이 아닌 정렬 알고리즘

 

종류	특징
기수 정렬	낮은 자릿수부터 높은 자릿수까지 정렬 자릿수에 올 수 있는 숫자별로 각각 큐를 생성해 각 자릿수에 해당하는 큐에 숫자를 넣으며 정렬 시간 복잡도 면에서 효율적이지만 메모리 소비가 큼
계수 정렬	데이터 범위를 인덱스로 갖는 배열을 생성해 각 인덱스에 해당하는 데이터 개수를 세서 정렬 수행

 

1. 최소 신장 트리(MST)

① 간선의 가중치 총합이 가장 작은 신장 트리

② 프림 알고리즘

• 시작 정점을 정한 후 트리를 확장해 최소 신장 트리를 생성하는 방식
• 방문 가능한 정점 중 비용이 적게 드는 정점을 선택해 트리 확장

③ 크루스칼 알고리즘

• 여러 트리를 합쳐 하나의 최소 신장 트리를 생성하는 방식
• 간선을 가중치에 따라 정렬한 뒤 낮은 가중치를 갖는 간선을 선택하여 여러 트리를 하나로 합쳐 나감

 

1. 최단 거리 알고리즘

① 그래프의 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘

② 다익스트라 알고리즘

• 간선의 가중치가 음수가 아닌 경우 최단 거리를 구하는 알고리즘
• 방문 가능한 정점 중 비용이 가장 적은 정점을 방문
• 방문한 정점과 연결된 다른 정점의 비용 갱신이 가능한 경우 갱신 수행

③ 벨만-포드 알고리즘

• 간선의 가중치가 음수인 경우까지 최단 거리를 구하는 알고리즘
• 음의 사이클이 있으면 알고리즘을 적용할 수 없음