DFS(깊이 우선 탐색)는 형제(sibling) 정점보다 자식(child) 정점을 먼저 방문하는 알고리즘입니다. 즉, 너비를 넓히며 탐색하기 전에 특정 경로의 깊이를 끝까지 따라 내려가는 방식으로 그래프를 순회합니다. DFS를 구현할 때는 일반적으로 스택(Stack)을 사용하며, 재귀 호출 시 프로그램의 콜 스택(call stack)이 이 역할을 대신 수행하기도 합니다.DFS의 동작 원리DFS는 다음과 같은 규칙에 따라 동작합니다.인접한 방문하지 않은 정점을 방문하고, 방문 처리한 뒤 화면에 표시하고 스택에 push합니다.방문하지

토폴로지 정렬이란?토폴로지 정렬(topological sort)은 방향 그래프(directed graph)의 정점들을 선형 순서로 나열하는 알고리즘입니다. 핵심 규칙은 간단합니다. 정점 u에서 정점 v로 향하는 방향 간선 U→V가 존재한다면, 정렬 결과에서 u는 반드시 v보다 앞에 위치해야 합니다. 따라서 토폴로지 정렬은 방향 그래프에서만 의미가 있습니다.토폴로지 정렬이 활용되는 실제 사례토폴로지 정렬은 실생활의 다양한 상황에서 매우 유용하게 사용됩니다.요리 레시피: 레시피에는 다음 단계로 넘어가기 전에 반드시 거쳐야 하는 필수 단

그래프 이론에서 최단 경로 문제(Shortest Path Problem)란 그래프에 존재하는 두 정점(vertex 또는 node) 사이를 연결하는 경로 중, 경로를 구성하는 간선(edge)들의 가중치 합이 최소가 되는 경로를 찾는 문제를 말합니다.최단 경로 알고리즘을 구현하려면 기존의 엣지 추가 메서드들이 단순히 노드 간 연결만 처리하던 것에서 한 단계 더 나아가, 각 간선에 가중치(weight)도 함께 저장할 수 있어야 합니다. 이를 위해 addEdge와 addDirectedEdge 메서드를 수정해 보겠습니다.가중치를 지원하는 엣

다익스트라 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 가중치 그래프(weighted graph)에서 노드 간의 최단 경로를 찾는 대표적인 알고리즘입니다. 그래프를 생성할 때 간선에 가중치를 부여하려면 앞서 소개한 addEdge와 addDirectedEdge 메서드를 활용합니다. 알고리즘 동작 원리 다익스트라 알고리즘은 다음과 같은 순서로 동작합니다. 거리(distances) 컬렉션 생성 — 시작 노드를 제외한 모든 정점의 거리를 무한대(Infinity)로 초기화합니다. 시작 노드를 우선순위 큐에 삽입 — 시작 노드의

다익스트라(Dijkstra) 알고리즘은 하나의 시작 노드에서 다른 모든 노드까지의 최단 거리와 경로를 구하는 데 사용됩니다. 하지만 경우에 따라서는 모든 노드에서 다른 모든 노드까지의 최단 경로를 한 번에 구해야 할 필요가 있습니다. 이럴 때 유용한 것이 바로 전체 쌍 최단 경로(All Pairs Shortest Path) 알고리즘이며, 그중 가장 널리 사용되는 것이 플로이드-워셜(Floyd-Warshall) 알고리즘입니다.플로이드-워셜 알고리즘의 동작 원리N x N 크기의 거리 행렬을 생성하고 모든 값을 무한대(Infinity)로

트리 순회란 무엇인가?트리 순회(Tree Traversal)는 트리 자료 구조에 포함된 모든 노드를 정확히 한 번씩 방문하는 과정을 의미합니다. 배열이나 연결 리스트처럼 선형적인 자료 구조와 달리, 트리는 계층적(hierarchical) 구조를 가지기 때문에 어떤 순서로 노드를 방문할지 결정하는 것이 중요한 문제가 됩니다.순회 방식의 분류 기준트리 순회는 노드를 방문하는 순서에 따라 여러 가지 방식으로 분류됩니다. 대표적인 순회 방법은 다음과 같습니다.전위 순회(Preorder Traversal): 루트 노드를 먼저 방문한 뒤, 왼

중위 순회(Inorder Traversal)는 트리를 순회하는 대표적인 방법 중 하나로, 왼쪽 서브트리를 먼저 방문한 뒤 루트(root) 노드를 거치고, 마지막으로 오른쪽 서브트리를 방문하는 방식입니다. 이때 항상 기억해야 할 점은 모든 노드가 그 자체로 하나의 서브트리가 될 수 있다는 사실입니다.이진 트리를 중위 순회하면 출력 결과가 키 값의 오름차순으로 정렬된 형태로 나타난다는 특징이 있습니다.A에서 출발하여 중위 순회 규칙에 따라 왼쪽 서브트리인 B로 이동합니다. B 역시 동일한 방식으로 중위 순회가 진행되며, 이 과정은 모든

전위 순회(Pre-order Traversal)는 트리를 탐색하는 대표적인 방법 중 하나로, 루트 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문합니다. 즉, 각 노드에 도달했을 때 자기 자신을 먼저 처리한 뒤 자식 노드들을 탐색하는 것이 특징입니다.전위 순회의 동작 원리아래 트리 구조를 예로 들어 살펴보겠습니다.루트 노드 A에서 시작한다고 가정해 봅시다. 전위 순회 규칙에 따라 먼저 A 자신을 방문하고, 그다음 왼쪽 서브트리인 B로 이동합니다. B 역시 같은 규칙으로 순회되며, 이 과정은 트리의 모든 노드를 방문할 때까지

후위 순회(Post-order Traversal)란? 후위 순회는 루트 노드를 가장 마지막에 방문하는 트리 순회 방식으로, 메서드의 이름 역시 여기서 유래했습니다. 순회 순서는 다음과 같습니다. 먼저 왼쪽 서브트리를 순회합니다. 그다음 오른쪽 서브트리를 순회합니다. 마지막으로 루트 노드를 방문합니다. A에서 시작해 후위 순회 규칙을 따라가면, 가장 먼저 왼쪽 서브트리인 B를 방문하게 됩니다. B 역시 동일한 후위 순회 방식으로 탐색되며, 이 과정은 모든 노드를 방문할 때까지 반복됩니다. 위 트리를 후위 순회한 결과는 다음과

트리(Tree)에서 노드를 제거하는 작업은 언뜻 보기에 상당히 복잡해 보일 수 있습니다. 노드를 삭제할 때는 노드의 구조에 따라 세 가지 경우를 고려해야 합니다. 이 글에서는 각 경우를 차례대로 살펴본 뒤, 지금까지의 패턴처럼 클래스 메서드와 재귀 호출용 헬퍼(helper) 함수로 나누어 구현하겠습니다. 노드 삭제의 3가지 경우 경우 1: 리프 노드(자식 없음) 삭제하려는 노드가 자식이 없는 리프 노드라면, 부모 노드와의 연결만 끊어주면 간단히 제거할 수 있습니다. 아래 예시에서 F를 제거해 보겠습니다. A /

이진 탐색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 저장하는 자료구조입니다. 이러한 규칙 덕분에 데이터 검색, 삽입, 삭제를 평균적으로 O(log n)의 시간 복잡도로 처리할 수 있어 정렬된 데이터를 다룰 때 매우 유용합니다.이번 글에서는 자바스크립트로 이진 탐색 트리 클래스를 직접 구현해 보겠습니다. 반복문 기반 방식과 재귀 기반 방식을 모두 다루며, 삽입·검색·최솟값/최댓값 조회·노드 삭제·순회(traversal)

AVL 트리란 무엇인가?AVL 트리는 1962년 이 알고리즘을 고안한 소련의 수학자 게오르기 아델슨-벨스키(Georgy Adelson-Velsky)와 예브게니 랜디스(Evgenii Landis)의 이름을 딴 자가 균형(self-balancing) 이진 탐색 트리입니다. 자가 균형 트리란 삽입과 삭제가 일어날 때마다 서브트리 내부에서 회전(rotation) 연산을 수행하여 왼쪽과 오른쪽의 균형을 스스로 유지하는 트리를 의미합니다.왜 균형이 중요한가?데이터가 한쪽 방향으로만 계속 삽입되면 일반적인 이진 탐색 트리는 연결 리스트처럼 한쪽

AVL 트리는 왼쪽 서브트리와 오른쪽 서브트리의 높이를 확인하고, 두 높이의 차이가 1을 초과하지 않도록 보장하는 자가 균형 이진 탐색 트리입니다. 이때 두 서브트리 높이의 차이를 균형 계수(Balance Factor)라고 부릅니다.예를 들어 아래 세 개의 트리를 살펴보면, 첫 번째 트리는 균형이 잡혀 있지만 나머지 두 트리는 균형이 깨져 있는 상태입니다.균형 계수의 이해두 번째 트리에서는 노드 C의 왼쪽 서브트리 높이가 2이고 오른쪽 서브트리 높이가 0이므로 차이가 2가 됩니다. 세 번째 트리에서는 노드 A의 오른쪽 서브트리 높이

AVL 트리는 스스로의 균형을 유지하기 위해 다음과 같은 네 가지 종류의 회전(rotation)을 수행할 수 있습니다.좌회전(Left Rotation)우회전(Right Rotation)좌-우 회전(Left-Right Rotation)우-좌 회전(Right-Left Rotation)앞의 두 가지는 단일 회전(single rotation)이고, 나머지 두 가지는 단일 회전을 조합한 이중 회전(double rotation)입니다. 트리가 불균형 상태가 되려면 최소한 높이가 2인 트리가 필요하므로, 이 간단한 트리를 예로 들어 각 회전 방

이번 글에서는 AVL 트리에 노드를 삽입하는 방법을 알아봅니다. AVL 트리에서의 삽입 절차는 일반적인 이진 탐색 트리(BST)와 동일하지만, 트리를 따라 내려가는 과정마다 균형 잡기(balance)라는 추가 단계를 수행해야 한다는 점이 다릅니다. 균형을 맞추려면 앞서 살펴본 균형 인수(balance factor)를 계산해야 합니다. 그리고 계산된 균형 상태에 따라 적절한 회전(rotation) 메서드를 호출하면 되는데, 이전 글의 회전 설명을 참고하면 어떤 상황에서 어떤 회전을 적용해야 하는지 직관적으로 이해할 수 있습니다. 그

프로그래밍을 하다 보면 두 개의 컨테이너를 조인(join) 함수로 결합하여 새로운 컨테이너를 만들어야 하는 경우가 종종 있습니다. 이번 글에서는 2개의 HashTable을 인자로 받아 모든 값을 포함하는 새로운 HashTable을 생성하는 정적(static) join 메서드를 직접 구현해 보겠습니다.구현을 단순하게 유지하기 위해, 두 해시 테이블에 동일한 키가 존재할 경우 두 번째 테이블의 값이 첫 번째 테이블의 값을 덮어쓰도록(override) 설계하겠습니다. 이는 객체 병합 시 일반적으로 사용되는 방식과 같습니다.join 메서드

해시테이블(HashTable)은 키(key)와 값(value)을 매핑해 저장하는 대표적인 자료구조입니다. 해시 함수가 키를 배열 인덱스로 변환해 주기 때문에 데이터의 검색·삽입·삭제를 평균 O(1)의 시간 복잡도로 처리할 수 있습니다. 자바스크립트에는 내장 Map 객체가 있지만, 해시테이블의 동작 원리를 깊이 이해하려면 직접 구현해 보는 것이 큰 도움이 됩니다.아래는 체이닝(chaining) 방식으로 충돌(collision)을 처리하는 HashTable 클래스의 전체 구현입니다. 물론 더 효율적인 자료구조와 충돌 해결 알고리즘을 적

트리 데이터 구조란 무엇인가? 트리(Tree)는 조직도, 파일 시스템처럼 계층적인 구조를 표현하는 대표적인 비선형 데이터 구조입니다. 배열이나 연결 리스트가 선형으로 데이터를 나열하는 것과 달리, 트리는 하나의 시작점에서 여러 갈래로 뻗어 나가는 부모-자식 관계를 통해 데이터를 저장합니다. 실제로 우리가 다루는 많은 것들이 트리 구조로 되어 있습니다. 예를 들어 웹 개발자라면 매일 접하게 되는 HTML DOM이 바로 트리의 전형적인 예이며, JSON 데이터, 폴더와 파일로 이루어진 디렉터리 구조, 회사의 조직도 등도 모두 트리로 모

이진 트리(Binary Tree)는 데이터 저장을 목적으로 사용되는 특수한 자료구조입니다. 이진 트리의 가장 큰 특징은 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 조건입니다.이진 트리는 정렬된 배열과 연결 리스트의 장점을 동시에 지니고 있습니다. 즉, 탐색 속도는 정렬된 배열처럼 빠르면서도, 삽입과 삭제 연산은 연결 리스트처럼 효율적으로 처리할 수 있습니다. 이러한 균형 잡힌 성능 덕분에 이진 트리는 다양한 알고리즘과 데이터 관리 시스템에서 널리 활용됩니다.아래는 이진 트리의 구조를 보여주는 예시 그림입니다.이진 트리의

이진 검색 트리란 무엇인가?이진 검색 트리(Binary Search Tree, BST)는 특별한 규칙을 따르는 트리 자료구조입니다. 모든 노드는 다음 두 가지 조건을 반드시 만족해야 합니다.왼쪽 자식 노드의 값은 항상 부모 노드의 값보다 작아야 합니다.오른쪽 자식 노드의 값은 항상 부모 노드의 값보다 커야 합니다.이러한 정렬 규칙 덕분에 이진 검색 트리에서는 값 검색, 삽입, 삭제 작업을 평균적으로 O(log n)의 시간 복잡도로 매우 효율적으로 수행할 수 있습니다. 데이터가 정렬된 상태로 유지되기 때문에 배열보다 빠른 탐색 성능을