하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 분할 정복(Divide and Conquer) 알고리즘입니다.
시간 복잡도는 최선, 평균, 최악 모두 O(n log n)으로 일정하며, 안정 정렬(Stable Sort)입니다.
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let i = 0, 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++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log("초기 배열:", arr);
console.log("정렬 결과:", mergeSort(arr));
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 정렬하는 분할 정복 알고리즘입니다. 실무에서 가장 널리 쓰이는 매우 빠른 정렬 알고리즘입니다.
평균 시간 복잡도는 O(n log n)이며, 최악의 경우(이미 정렬된 경우) O(n²)이 될 수 있습니다.
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[arr.length - 1]; // 마지막 원소를 피벗으로 선택
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const arr = [5, 3, 8, 4, 9, 1, 6];
console.log("초기 배열:", arr);
console.log("정렬 결과:", quickSort(arr));
트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 알고리즘입니다.
주로 재귀호출이나 스택(Stack)을 이용하여 구현하며, 미로 찾기 등 백트래킹에 주로 사용됩니다.
const graph = {
1: [2, 3],
2: [4, 5],
3: [6, 7],
4: [],
5: [],
6: [],
7: []
};
function dfs(graph, startNode) {
const visited = new Set();
const result = [];
function explore(node) {
if (visited.has(node)) return;
visited.add(node);
result.push(node);
console.log(`현재 방문 노드: ${node}`);
for (const neighbor of graph[node]) {
explore(neighbor);
}
}
explore(startNode);
return result;
}
console.log("DFS 탐색 결과:", dfs(graph, 1).join(" -> "));
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문합니다.
주로 큐(Queue)를 이용하여 구현하며, 최단 경로를 찾을 때 많이 사용됩니다.
const graph = {
1: [2, 3],
2: [4, 5],
3: [6, 7],
4: [],
5: [],
6: [],
7: []
};
function bfs(graph, startNode) {
const visited = new Set([startNode]);
const queue = [startNode];
const result = [];
while (queue.length > 0) {
const node = queue.shift(); // 큐에서 꺼내기
result.push(node);
console.log(`현재 방문 노드: ${node}`);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor); // 큐에 삽입
}
}
}
return result;
}
console.log("BFS 탐색 결과:", bfs(graph, 1).join(" -> "));
복잡한 문제를 여러 개의 간단한 하위 문제(Sub-problem)로 나누어 푸는 방법입니다. 하위 문제들의 계산 결과를 저장(Memoization)하여 중복 계산을 방지하는 것이 핵심입니다.
일반 재귀호출의 시간 복잡도 O(2^n)을 O(n) 수준으로 최적화할 수 있습니다.
// 메모이제이션을 위한 객체 (캐시)
const memo = {};
function fibonacci(n) {
if (n <= 1) return n;
// 이미 계산한 적이 있다면 캐시된 값을 즉시 반환
if (memo[n]) {
console.log(`F(${n})은 캐시에서 가져옴: ${memo[n]}`);
return memo[n];
}
console.log(`F(${n}) 계산 중...`);
// 계산 결과를 캐시에 저장
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
console.log("피보나치 5번째 수 구하기:");
console.log("결과:", fibonacci(5));
다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾습니다. (단, 음의 간선이 없을 때만 정상 작동합니다)
각 노드에 대해 이전에 저장된 최단 거리와 현재 노드를 거쳐가는 거리를 비교하여 계속해서 최소값을 갱신해나가는 방식입니다.
const graph = {
A: { B: 2, C: 5 },
B: { C: 1, D: 3 },
C: { D: 6 },
D: {}
};
function dijkstra(graph, start) {
const distances = {};
for (let node in graph) distances[node] = Infinity;
distances[start] = 0;
const visited = new Set();
while (true) {
let currNode = null;
let shortestDistance = Infinity;
// 가장 가까운 미방문 노드 찾기
for (let node in distances) {
if (!visited.has(node) && distances[node] < shortestDistance) {
shortestDistance = distances[node];
currNode = node;
}
}
if (currNode === null) break;
visited.add(currNode);
console.log(`현재 노드 ${currNode} 방문. 최단 거리: ${shortestDistance}`);
// 인접 노드 거리 갱신
for (let neighbor in graph[currNode]) {
let distance = distances[currNode] + graph[currNode][neighbor];
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
}
}
}
return distances;
}
console.log("최종 최단 거리:", dijkstra(graph, 'A'));
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.
평균 시간 복잡도는 O(n²)이지만, 거의 정렬되어 있는 상태에서는 O(n)에 가까운 매우 빠른 속도를 보여줍니다.
function insertionSort(arr) {
const n = arr.length;
console.log("초기 배열:", arr);
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
// key보다 큰 값들은 한 칸씩 오른쪽으로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
const arr = [5, 3, 1, 4, 2];
console.log("정렬 결과:", insertionSort(arr));
정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값과 비교를 통해 탐색 범위를 반으로 줄여나갑니다.
시간 복잡도는 O(log n)으로 매우 빠르지만, 반드시 정렬된 상태에서만 사용할 수 있습니다.
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
console.log(`탐색 범위: index ${left} ~ ${right}, 중간값: ${arr[mid]}`);
if (arr[mid] === target) {
return mid; // 찾은 값의 인덱스 반환
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 값을 찾지 못한 경우
}
const sortedArr = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 11;
console.log("배열:", sortedArr);
console.log(`타겟 ${target}의 인덱스:`, binarySearch(sortedArr, target));
버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다. 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환합니다.
시간 복잡도는 O(n²)로 느리지만 구현이 가장 단순합니다.
function bubbleSort(arr) {
const n = arr.length;
console.log("초기 배열:", arr);
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
const arr = [5, 3, 1, 4, 2];
console.log("정렬 결과:", bubbleSort(arr));
선택 정렬은 제자리 정렬 알고리즘의 하나로, 해당 순서에 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘입니다.
시간 복잡도는 O(n²)이며 불안정 정렬(Unstable Sort)입니다.
function selectionSort(arr) {
const n = arr.length;
console.log("초기 배열:", arr);
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Swap
let temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
return arr;
}
const arr = [5, 3, 1, 4, 2];
console.log("정렬 결과:", selectionSort(arr));