알고리즘
알아두면 좋은 알고리즘 종류 및 시간복잡도
태태개발자
2023. 7. 11. 10:19
반응형
프로그래밍 알고리즘 종류
정렬
- 선택정렬 : O(n^2)
function selectionSort(arr) {
const length = arr.length;
for (let i = 0; i < length - 1; i++) {
let minIndex = i;
// 최솟값을 찾기 위해 배열을 순회합니다.
for (let j = i + 1; j < length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 최솟값을 현재 위치와 교환합니다.
const temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
// 테스트용 배열
const arr = [64, 25, 12, 22, 11];
console.log("정렬 전:", arr);
console.log("정렬 후:", selectionSort(arr));- 버블정렬 : O(n^2)
function bubbleSort(arr) {
const length = arr.length;
for (let i = 0; i < length - 1; i++) {
// 현재 루프에서 스왑이 발생하지 않으면 이미 정렬된 상태이므로 종료합니다.
let swapped = false;
for (let j = 0; j < length - i - 1; j++) {
// 현재 요소와 다음 요소를 비교하여 순서를 바꿉니다.
if (arr[j] > arr[j + 1]) {
// 스왑
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
// 스왑이 발생하지 않으면 정렬이 완료된 것이므로 종료합니다.
if (!swapped) break;
}
return arr;
}
// 테스트용 배열
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전:", arr);
console.log("정렬 후:", bubbleSort(arr));
- 삽입정렬 : O(n^2)
function insertionSort(arr) {
const length = arr.length;
for (let i = 1; i < length; i++) {
const current = arr[i];
let j = i - 1;
// 현재 요소를 이미 정렬된 부분의 적절한 위치에 삽입합니다.
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
// 테스트용 배열
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전:", arr);
console.log("정렬 후:", insertionSort(arr));
- 퀵정렬 : 평균 O(n log n), 최악 O(n^2)
function quickSort(arr, left = 0, right = arr.length - 1) {
if (arr.length > 1) {
const index = partition(arr, left, right);
if (left < index - 1) {
quickSort(arr, left, index - 1);
}
if (index < right) {
quickSort(arr, index, right);
}
}
return arr;
}
function partition(arr, left, right) {
const pivot = arr[Math.floor((left + right) / 2)];
let i = left;
let j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
j--;
}
}
return i;
}
// 테스트용 배열
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전:", arr);
console.log("정렬 후:", quickSort(arr));
- 병합정렬 : O(n log n)
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
// 테스트용 배열
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전:", arr);
console.log("정렬 후:", mergeSort(arr));- 힙정렬 : O(n log n)
function heapSort(arr) {
const length = arr.length;
// 최대 힙을 구성합니다.
for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
heapify(arr, length, i);
}
// 힙 정렬을 수행합니다.
for (let i = length - 1; i > 0; i--) {
// 최대 힙의 루트(가장 큰 값)를 마지막 요소와 교환합니다.
[arr[0], arr[i]] = [arr[i], arr[0]];
// 힙의 크기를 하나씩 줄여가며 힙 속성을 유지합니다.
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, heapSize, index) {
let largest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
// 왼쪽 자식 노드가 힙 범위 내에 있고 현재 값보다 크다면 largest를 업데이트합니다.
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
// 오른쪽 자식 노드가 힙 범위 내에 있고 현재 값보다 크다면 largest를 업데이트합니다.
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
// largest가 변경되었다면 현재 노드와 largest 위치의 값을 교환하고, 재귀적으로 heapify를 호출합니다.
if (largest !== index) {
[arr[index], arr[largest]] = [arr[largest], arr[index]];
heapify(arr, heapSize, largest);
}
}
// 테스트용 배열
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전:", arr);
console.log("정렬 후:", heapSort(arr));
탐색
- 이진탐색 : O(log n)
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid; // 타겟을 찾았을 때 인덱스 반환
} else if (arr[mid] < target) {
left = mid + 1; // 중간값보다 큰 범위를 탐색하기 위해 왼쪽 범위를 업데이트
} else {
right = mid - 1; // 중간값보다 작은 범위를 탐색하기 위해 오른쪽 범위를 업데이트
}
}
return -1; // 타겟을 찾지 못한 경우 -1 반환
}
// 테스트용 배열
const arr = [11, 22, 34, 45, 56, 67, 78, 89, 90];
const target = 45;
console.log("배열:", arr);
console.log(`타겟 ${target}의 인덱스:`, binarySearch(arr, target));
- 순차탐색 : O(n)
function sequentialSearch(arr, target) {
const length = arr.length;
for (let i = 0; i < length; i++) {
if (arr[i] === target) {
return i; // 타겟을 찾았을 때 인덱스 반환
}
}
return -1; // 타겟을 찾지 못한 경우 -1 반환
}
// 테스트용 배열
const arr = [11, 22, 34, 45, 56, 67, 78, 89, 90];
const target = 45;
console.log("배열:", arr);
console.log(`타겟 ${target}의 인덱스:`, sequentialSearch(arr, target));
그래프
v : 정점, e : 간선
- 너비우선탐색(BFS) : O(v+e)
class Graph {
constructor() {
this.adjacencyList = new Map();
}
addVertex(vertex) {
this.adjacencyList.set(vertex, []);
}
addEdge(v1, v2) {
this.adjacencyList.get(v1).push(v2);
this.adjacencyList.get(v2).push(v1);
}
bfs(startVertex) {
const visited = new Set();
const queue = [];
visited.add(startVertex);
queue.push(startVertex);
while (queue.length > 0) {
const currentVertex = queue.shift();
console.log(currentVertex);
const neighbors = this.adjacencyList.get(currentVertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
}
// 테스트
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.bfs("A");
- 깊이우선탐색(DFS) : O(v+e)
class Graph {
constructor() {
this.adjacencyList = new Map();
}
addVertex(vertex) {
this.adjacencyList.set(vertex, []);
}
addEdge(v1, v2) {
this.adjacencyList.get(v1).push(v2);
this.adjacencyList.get(v2).push(v1);
}
dfsRecursive(startVertex) {
const visited = new Set();
this.dfsRecursiveHelper(startVertex, visited);
}
dfsRecursiveHelper(vertex, visited) {
visited.add(vertex);
console.log(vertex);
const neighbors = this.adjacencyList.get(vertex);
for (let neighbor of neighbors) {
if (!visited.has(neighbor)) {
this.dfsRecursiveHelper(neighbor, visited);
}
}
}
dfsIterative(startVertex) {
const visited = new Set();
const stack = [];
stack.push(startVertex);
while (stack.length > 0) {
const currentVertex = stack.pop();
if (!visited.has(currentVertex)) {
visited.add(currentVertex);
console.log(currentVertex);
const neighbors = this.adjacencyList.get(currentVertex);
for (let neighbor of neighbors) {
stack.push(neighbor);
}
}
}
}
}
// 테스트
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.dfsRecursive("A");
// 또는
// graph.dfsIterative("A");
- 다익스트라 알고리즘(최단경로) : O((V + E) log V)
function Graph() {
this.adjacencyList = {};
}
Graph.prototype.addVertex = function (vertex) {
this.adjacencyList[vertex] = {};
};
Graph.prototype.addEdge = function (v1, v2, weight) {
this.adjacencyList[v1][v2] = weight;
this.adjacencyList[v2][v1] = weight;
};
Graph.prototype.dijkstra = function (startVertex) {
var distances = {};
var visited = {};
var queue = new PriorityQueue();
// 모든 정점까지의 거리를 Infinity로 초기화
for (var vertex in this.adjacencyList) {
distances[vertex] = Infinity;
}
distances[startVertex] = 0;
queue.enqueue(startVertex, 0);
while (!queue.isEmpty()) {
var currentVertex = queue.dequeue().element;
if (visited[currentVertex]) {
continue;
}
visited[currentVertex] = true;
var neighbors = this.adjacencyList[currentVertex];
for (var neighbor in neighbors) {
var weight = neighbors[neighbor];
var distance = distances[currentVertex] + weight;
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
queue.enqueue(neighbor, distance);
}
}
}
return distances;
};
function PriorityQueue() {
this.queue = [];
}
PriorityQueue.prototype.enqueue = function (element, priority) {
this.queue.push({ element: element, priority: priority });
this.sort();
};
PriorityQueue.prototype.dequeue = function () {
return this.queue.shift();
};
PriorityQueue.prototype.sort = function () {
this.queue.sort(function (a, b) {
return a.priority - b.priority;
});
};
PriorityQueue.prototype.isEmpty = function () {
return this.queue.length === 0;
};
// 테스트
var graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "D", 5);
graph.addEdge("C", "D", 1);
graph.addEdge("C", "E", 3);
graph.addEdge("D", "E", 7);
console.log(graph.dijkstra("A"));
- 벨만포드 알고리즘(최단경로) : O(V * E)
function bellmanFord(graph, startVertex) {
const vertices = Object.keys(graph);
const distances = {};
// 모든 정점까지의 거리를 Infinity로 초기화
for (let vertex of vertices) {
distances[vertex] = Infinity;
}
distances[startVertex] = 0;
// 간선 개수만큼 반복하여 최단 거리 업데이트
for (let i = 0; i < vertices.length - 1; i++) {
let updated = false; // 업데이트 발생 여부
for (let vertex of vertices) {
for (let neighbor in graph[vertex]) {
const weight = graph[vertex][neighbor];
const distance = distances[vertex] + weight;
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
updated = true; // 업데이트가 발생했음을 표시
}
}
}
// 업데이트가 발생한 경우에 한하여 음수 사이클 확인
if (i === vertices.length - 1 && updated) {
for (let vertex of vertices) {
for (let neighbor in graph[vertex]) {
const weight = graph[vertex][neighbor];
const distance = distances[vertex] + weight;
if (distance < distances[neighbor]) {
console.log("음수 사이클이 존재합니다.");
return;
}
}
}
}
}
return distances;
}
// 그래프 정의
const graph = {
A: { B: -1, C: 4 },
B: { C: 3, D: 2, E: 2 },
C: {},
D: { B: 1, C: 5 },
E: { D: -3 },
};
// 테스트
const startVertex = "A";
const shortestDistances = bellmanFord(graph, startVertex);
console.log(shortestDistances);
- 크루스칼 알고리즘(최소 비용 신장 트리) : O(E log E + E)
class DisjointSet {
constructor() {
this.parent = {};
this.rank = {};
}
makeSet(vertex) {
this.parent[vertex] = vertex;
this.rank[vertex] = 0;
}
find(vertex) {
if (this.parent[vertex] !== vertex) {
this.parent[vertex] = this.find(this.parent[vertex]);
}
return this.parent[vertex];
}
union(vertex1, vertex2) {
const root1 = this.find(vertex1);
const root2 = this.find(vertex2);
if (root1 !== root2) {
if (this.rank[root1] < this.rank[root2]) {
this.parent[root1] = root2;
} else if (this.rank[root1] > this.rank[root2]) {
this.parent[root2] = root1;
} else {
this.parent[root2] = root1;
this.rank[root1]++;
}
}
}
}
function kruskal(graph) {
const edges = [];
const minimumSpanningTree = [];
// 모든 간선 추출
for (let vertex in graph) {
for (let neighbor in graph[vertex]) {
edges.push([vertex, neighbor, graph[vertex][neighbor]]);
}
}
// 간선 가중치를 기준으로 정렬
edges.sort((a, b) => a[2] - b[2]);
const disjointSet = new DisjointSet();
// 각 정점에 대해 독립적인 집합 생성
for (let vertex in graph) {
disjointSet.makeSet(vertex);
}
// 가장 작은 가중치 간선부터 선택
for (let edge of edges) {
const [vertex1, vertex2, weight] = edge;
// 사이클이 생성되지 않는 경우에만 간선 선택
if (disjointSet.find(vertex1) !== disjointSet.find(vertex2)) {
disjointSet.union(vertex1, vertex2);
minimumSpanningTree.push(edge);
}
}
return minimumSpanningTree;
}
// 그래프 정의
const graph = {
A: { B: 7, D: 5 },
B: { A: 7, D: 9, C: 8, E: 7 },
C: { B: 8, E: 5 },
D: { A: 5, B: 9, E: 15, F: 6 },
E: { B: 7, C: 5, D: 15, F: 8, G: 9 },
F: { D: 6, E: 8, G: 11 },
G: { E: 9, F: 11 },
};
// 테스트
const minimumSpanningTree = kruskal(graph);
console.log(minimumSpanningTree);
- 프림 알고리즘(최소 비용 신장 트리) : O(E log V + V)
class Graph {
constructor() {
this.adjacencyList = new Map();
}
addVertex(vertex) {
this.adjacencyList.set(vertex, new Map());
}
addEdge(v1, v2, weight) {
this.adjacencyList.get(v1).set(v2, weight);
this.adjacencyList.get(v2).set(v1, weight);
}
prim(startVertex) {
const minimumSpanningTree = new Map();
const visited = new Set();
const priorityQueue = new PriorityQueue();
// 시작 정점을 방문 처리
visited.add(startVertex);
// 시작 정점과 연결된 간선들을 우선순위 큐에 삽입
const edges = this.adjacencyList.get(startVertex);
for (let [vertex, weight] of edges.entries()) {
priorityQueue.enqueue({ vertex, weight });
}
while (!priorityQueue.isEmpty()) {
const { vertex, weight } = priorityQueue.dequeue();
// 이미 방문한 정점이면 건너뛰기
if (visited.has(vertex)) {
continue;
}
// 정점을 방문 처리하고, 최소 비용 간선을 minimumSpanningTree에 추가
visited.add(vertex);
minimumSpanningTree.set(vertex, weight);
// 현재 정점과 연결된 간선들을 우선순위 큐에 삽입
const edges = this.adjacencyList.get(vertex);
for (let [v, w] of edges.entries()) {
if (!visited.has(v)) {
priorityQueue.enqueue({ vertex: v, weight: w });
}
}
}
return minimumSpanningTree;
}
}
// 우선순위 큐(Priority Queue) 구현
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue({ vertex, weight }) {
this.queue.push({ vertex, weight });
this.sort();
}
dequeue() {
return this.queue.shift();
}
sort() {
this.queue.sort((a, b) => a.weight - b.weight);
}
isEmpty() {
return this.queue.length === 0;
}
}
// 그래프 생성
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "D", 5);
graph.addEdge("C", "D", 1);
graph.addEdge("C", "E", 3);
graph.addEdge("D", "E", 7);
// 테스트
const minimumSpanningTree = graph.prim("A");
console.log(minimumSpanningTree);
- 개선된 프림 알고리즘(최소 비용 신장 트리) : O(E log E + V)
* 기존 우선순위 큐를 힙 자료구조를 사용하여 가장 작은 가중치의 간선을 선택하여 속도를 개선
class Graph {
constructor() {
this.adjacencyList = new Map();
}
addVertex(vertex) {
this.adjacencyList.set(vertex, new Map());
}
addEdge(v1, v2, weight) {
this.adjacencyList.get(v1).set(v2, weight);
this.adjacencyList.get(v2).set(v1, weight);
}
prim(startVertex) {
const minimumSpanningTree = new Map();
const visited = new Set();
const heap = new Heap();
// 시작 정점을 방문 처리
visited.add(startVertex);
// 시작 정점과 연결된 간선들을 힙에 삽입
const edges = this.adjacencyList.get(startVertex);
for (let [vertex, weight] of edges.entries()) {
heap.insert({ vertex, weight });
}
while (!heap.isEmpty()) {
const { vertex, weight } = heap.deleteMin();
// 이미 방문한 정점이면 건너뛰기
if (visited.has(vertex)) {
continue;
}
// 정점을 방문 처리하고, 최소 비용 간선을 minimumSpanningTree에 추가
visited.add(vertex);
minimumSpanningTree.set(vertex, weight);
// 현재 정점과 연결된 간선들을 힙에 삽입
const edges = this.adjacencyList.get(vertex);
for (let [v, w] of edges.entries()) {
if (!visited.has(v)) {
heap.insert({ vertex: v, weight: w });
}
}
}
return minimumSpanningTree;
}
}
// 힙(Heap) 구현
class Heap {
constructor() {
this.heap = [];
}
insert(element) {
this.heap.push(element);
this.heapifyUp(this.heap.length - 1);
}
deleteMin() {
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.heapifyDown(0);
}
return min;
}
heapifyUp(index) {
const parentIndex = Math.floor((index - 1) / 2);
if (parentIndex >= 0 && this.heap[parentIndex].weight > this.heap[index].weight) {
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
this.heapifyUp(parentIndex);
}
}
heapifyDown(index) {
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
let smallestIndex = index;
if (leftChildIndex < this.heap.length && this.heap[leftChildIndex].weight < this.heap[smallestIndex].weight) {
smallestIndex = leftChildIndex;
}
if (rightChildIndex < this.heap.length && this.heap[rightChildIndex].weight < this.heap[smallestIndex].weight) {
smallestIndex = rightChildIndex;
}
if (smallestIndex !== index) {
[this.heap[index], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[index]];
this.heapifyDown(smallestIndex);
}
}
isEmpty() {
return this.heap.length === 0;
}
}
// 그래프 생성
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "D", 5);
graph.addEdge("C", "D", 1);
graph.addEdge("C", "E", 3);
graph.addEdge("D", "E", 7);
// 테스트
const minimumSpanningTree = graph.prim("A");
console.log(minimumSpanningTree);
문제 해결전략
- 재귀호출 : O(k^n) : n은 재귀 호출의 횟수이고, k는 각 재귀 호출 당 수행되는 연산의 수
- 함수가 자기 자신을 호출하여 문제를 해결하는 방법입니다.
- 주어진 문제를 더 작은 하위 문제로 분할하고, 재귀적으로 해결합니다.
- 종료 조건을 설정하여 재귀 호출을 멈추게 합니다.
- 동적계획법 : O(n * m), 여기서 n은 하위 문제의 개수이고 m은 각 하위 문제의 연산 시간 복잡도
- 큰 문제를 작은 하위 문제로 나누어 해결하고, 중복되는 계산을 피하는 방법입니다.
- 작은 하위 문제의 해를 저장하고, 이를 활용하여 큰 문제를 해결합니다.
- Memoization(메모이제이션) 기법을 사용하여 중복 계산을 피합니다.
- 분할정복
- 문제를 더 작은 하위 문제로 분할하고, 각 하위 문제를 독립적으로 해결합니다.
- 작은 문제의 해를 결합하여 원래 문제의 해를 얻습니다.
- 재귀 호출을 사용하여 문제를 분할하고 해결합니다.
- 탐욕 알고리즘
- 각 단계에서 지금 당장 가장 좋은 선택을 하는 알고리즘입니다.
- 최적해를 구하는 것이 목표이지만, 항상 최적해를 보장하지는 않습니다.
- 현재 상황에서 가장 유리한 선택을 반복하여 전체적인 최적해를 찾습니다.
- 백트래킹
- 해를 찾기 위해 모든 가능한 후보군을 탐색하고, 불필요한 후보군은 배제합니다.
- 한 단계씩 진행하다가 현재 상태에서 해를 찾지 못하면 이전 단계로 되돌아가 다른 후보를 탐색합니다.
- DFS(Depth-First Search)와 재귀 호출을 활용합니다.
반응형