정렬 알고리즘
정렬 알고리즘은 데이터를 특정 기준에 따라 나열하는 알고리즘이다.
사용 사례
데이터의 정렬이 필요할 때 사용한다.
일반적으로 빠른 성능이 필요하다면 퀵 정렬을, 데이터가 크고 안정적인 정렬이 필요하다면 병합 정렬을, 데이터가 거의 정렬되어 있다면 삽입 정렬을 선택하는 게 좋다.
종류
-
버블 정렬 (Bubble Sort)
- 인접한 두 값을 비교해 순서를 바꾼다.
- 시간복잡도는 O(n²)이다.
- 사용 사례 : 데이터 양이 적고, 코드 구현이 간단해야 하는 경우
-
선택 정렬 (Selection Sort)
- 맨 앞에서부터 위치에 적절한 값을 선택해 교환한다.
- 시간복잡도는 O(n²)이다.
- 사용 사례 : 데이터의 크기가 작고, 메모리 공간이 부족한 경우. 추가적인 메모리 사용이 거의 없다.
-
삽입 정렬 (Insertion Sort)
- 새로운 값을 이미 정렬된 부분에 삽입한다.
- 시간복잡도는 O(n²)이다.
- 사용 사례 : 데이터가 거의 정렬된 경우, 또는 데이터 양이 적은 경우. 실시간으로 입력되는 데이터를 정렬해야 할 때.
-
병합 정렬 (Merge Sort)
- 데이터를 반으로 나눈 후 정렬하여 다시 병합한다.
- 시간복잡도는 O(n log n)이다.
- 사용 사례 : 데이터 양이 많을 때. 데이터의 크기가 커도 효율적으로 동작하지만 추가 메모리가 필요하다.
-
퀵 정렬 (Quick Sort)
- 피벗을 선택해 그보다 작은 값과 큰 값을 분할한 후, 각 부분을 재귀적으로 정렬한다.
- 시간복잡도는 O(n log n)이다.
- 사용 사례 : 일반적으로 널리 사용된다. 피벗 선택에 따라 성능이 크게 달라질 수 있으며, 최악의 경우 O(n²)이 될 수 있다.
-
힙 정렬 (Heap Sort)
- 힙 자료구조를 사용해 값을 정렬한다.
- 시간복잡도는 O(n log n)이다.
- 사용 사례 : 안정성이 필요하지 않은 경우. 데이터 양이 많을 때도 효율적으로 동작하며, 추가 메모리가 필요하지 않다.
탐색 알고리즘
데이터에서 원하는 값을 찾을 때 사용하는 알고리즘이다.
사용 사례
데이터 구조와 탐색 목표에 따라 적절한 알고리즘을 선택해야 한다.
정렬되지 않은 배열에서 탐색할 때는 선형 탐색을, 정렬된 배열에서 효율적으로 탐색할 때는 이진 탐색을, 그래프를 탐색할 때는 DFS나 BFS를 사용한다.
종류
-
선형 탐색 (Linear Search)
- 데이터를 처음부터 끝까지 순차적으로 확인하며 원하는 값을 찾는다. 정렬되지 않은 데이터에서도 사용할 수 있다.
- 시간복잡도는 O(n)이다.
- 사용 사례 : 정렬되지 않았거나 정렬 여부를 알 수 없는 경우, 데이터 크기가 작아서 시간복잡도가 중요하지 않은 경우.
-
이진 탐색 (Linear Search)
- 정렬된 배열에서 중앙 값을 기준으로 탐색 범위를 반으로 줄여가며 값을 찾는다.
- 시간복잡도는 O(log n)이다.
- 사용 사례 : 배열이 이미 정렬된 상태일 때. 데이터의 크기가 크고 빠른 탐색이 요구될 때.
완전탐색 알고리즘
가능한 모든 경우를 전부 탐색하여 답을 찾는 알고리즘이다.
종류
-
브루트 포스 (Brute Force)
- 가능한 모든 방법을 찾아 검사하여 해답을 찾는다.
-
순열 (Permutation)
- 주어진 원소를 나열하는 모든 가능한 순서를 생성해 가능한 모든 경우의 수를 확인한다.
- 사용 사례 : 주어진 숫자들로 만들 수 있는 가장 큰 수, 특정 조건을 만족하는 순서.
-
백트래킹 (Backtracking)
- 가능한 모든 방법을 탐색하다가, 조건이 맞지 않는 경우 되돌아간다.
- 사용 사례 : 스도쿠, N-Queens 문제, 조건을 만족하는 경로 찾기.
-
비트마스크 (Bitmask)
- 이진수를 사용해 부분집합을 표현하고 처리한다. 각 비트는 원소의 포함 여부를 나타낸다.
- 사용 사례 : 부분집합을 빠르게 생성해야 할 때. 상태를 비트로 표현할 수 있을 때.
-
재귀 (Recursion)
- 복잡한 문제를 간단한 문제로 나누어 해결하는 방법이다.
- 사용 사례 : 하노이의 탑
그래프 알고리즘
노드와 간선으로 표현되는 관계를 탐색할 때 사용하는 알고리즘이다.
종류
-
깊이 우선 탐색 (DFS)
- 시작 정점에서 가능한 깊게 들어가며 탐색한 후, 더 이상 탐색할 수 없으면 되돌아가는 방식이다. 스택을 사용하거나 재귀적으로 구현한다.
- 사용 사례 : 경로 탐색, 연결 요소 찾기, 미로 찾기
-
너비 우선 탐색 (BFS)
- 시작 정점에서 인접한 정점을 먼저 탐색하고, 그 다음 인접한 정점을 탐색하는 방식이다. 큐를 사용해 구현한다.
- 사용 사례 : 최단 경로 문제, 레별 별 탐색
-
다익스트라 알고리즘 (Dijkstra's Algorithm)
- 가중치가 있는 그래프에서 최단 경로를 찾는다. 음의 가중치가 있는 간선은 처리할 수 없다.
- 사용 사례 : 최단 거리 경로 찾기
-
크루스칼 알고리즘 (Kruskal's Algorithm)
- 그래프의 모든 간선을 가중치 순으로 정렬하고, 가장 작은 가중치의 간선을 선택해 사이클이 생기지 않도록 트리를 확장한다.
- 사용 사례 : 최소 비용으로 모든 정점 연결
