✅ 다익스트라 알고리즘(Dijkstra's Algorithm)이란? 그래프 내의 한 출발점에서 모든 다른 노드까지의 최단 경로를 찾는 데 사용되는 알고리즘으로 가중치가 있는 그래프에서 각 노드 사이의 최단 경로를 찾을 때 효과적으로 사용된다. 사용 사례 도로 네트워크 경로 탐색: 다익스트라 알고리즘은 GPS 시스템과 네비게이션 앱에서 사용된다. 운전자가 출발지와 목적지를 입력하면, 다익스트라 알고리즘을 활용하여 최단 경로와 예상 도착 시간을 계산하고 제공한다. 인터넷 라우팅: 다익스트라 알고리즘은 데이터 패킷을 최적 경로로 전달하는 라우팅 프로토콜에서 사용된다. 네트워크 노드 간의 연결을 나타내는 그래프에서 최단 경로를 계산하여 데이터의 효율적인 전달을 도와준다. 공항 및 항구 관리: 항공국 및 항구 관..
✅ 그래프(Graphs)란? 객체 간의 관계를 표현하는 데 사용됩니다. 그래프는 노드(node)들과 이들을 연결하는 간선(edge)들의 집합으로 구성된다. 노드는 그래프 안에 있는 개별 요소를 나타내며, 종종 정점(vertex)이라고도 부른다. 노드는 어떤 유형의 데이터나 객체를 담을 수 있으며, 각 노드는 고유한 식별자로 구분된다. 간선(edge)은 노드 사이의 관계를 나타내는 연결선이다. 간선은 노드 간의 관계를 나타내는 데 사용되며, 방향성이 있는 경우도 있고 없는 경우도 있다. 방향성이 없는 그래프에서는 간선이 양방향으로 표현되며, 방향성이 있는 그래프에서는 한 방향으로의 연결만을 나타낸다. 연결 리스트의 경우 노드들이 직선으로 연결되어 있었고, 트리(트리는 그래프의 일종) 같은 경우 한 개의 루..
✅ 해시 테이블(Hash Tables)이란? 데이터를 저장하고 검색하는 데 사용되는 자료구조 중 하나입니다. 해시 테이블은 키(Key)와 값(Value)으로 이루어진 항목(Item)을 저장합니다. 해시 테이블은 배열(Array)과 유사한 구조를 가지고 있지만 배열과는 달리 인덱스(Index)가 정수가 아니라 키(Key)로 구성됩니다. 즉, 순서를 가지지 않습니다. 키(Key)는 해시 함수(Hash function)를 사용하여 배열의 인덱스로 변환됩니다. 해시 함수는 키(Key)를 해시값(Hash value)으로 매핑하는 함수입니다. 해시 함수는 입력이 동일하면 항상 동일한 해시값(Hash value)을 반환해야 합니다. 해시값(Hash value)은 배열의 인덱스와 같이 정수값이어야 합니다. 해시 테이블..
✅ 힙(Heap)이란? 힙(Heap)은 자료 구조 중 하나로, 일반적으로 우선순위 큐(Priority Queue)를 구현하는 데 사용된다. 힙은 완전 이진트리(Complete Binary Tree) 구조를 가지며, 부모 노드와 자식 노드 간에 우선순위 관계를 가진다. * 완전 이진트리 - 모든 노드가 왼쪽 자식과 오른쪽 자식을 가진 이진트리로서, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있는 이진트리를 말한다. 마지막 레벨은 왼쪽에서부터 오른쪽으로 채워지는 형태이다. 🟢이진 힙(Binary Heap) 힙의 한 종류로, 모든 노드는 최대 두 개의 자식 노드를 가지며, 주로 배열을 사용하여 구현된다. 🟡 이진 힙의 두 종류 최대 힙(Max Heap): 부모 노드는 자식 노드보다 항상 크거나 같은 값을 가짐...
✅ 깊이 우선 탐색(DFS, Depth-First Search) 트리 또는 그래프를 탐색하는 알고리즘으로, 시작점에서 출발하여 가능한 한 깊숙이 탐색해 나가는 방법이다. 이러한 방식으로 트리를 순회할 때, 전위 순회(Pre-Order)는 DFS 중에서도 가장 일반적인 방법 중 하나이며, 전위 순회 외에도 중위 순회(In-Order)나 후위 순회(Post-Order) 등도 DFS의 한 종류이다. 🤔 깊이 우선 탐색의 특징 스택이나 재귀 함수를 이용해서 구현 가능하다. 탐색 경로를 기억하지 않아, 특정한 경로를 찾는 문제에는 너비 우선 탐색(BFS)이 더 적합하다. 구현이 쉽고 속도가 빠르다. 한번 방문한 노드를 다시 방문하지 않는 것이 아니기에 무한 그래프에 빠질 위험이 있다. 이를 방지하기 위해 탐색 깊..
✅ 트리 순회(Tree Trabersal)란? 트리 순회는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이진트리뿐만 아니라 모든 트리에서도 일반화될 수 있다. 트리를 순회하는 데는 두 가지 전략이 존재한다. 너비 우선 탐색(BFS, Breadth-first Search) 깊이 우선 탐색(DFS, Depth-first Search) 🤔 너비 우선 탐색(BFS, Breadth-first Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 👍 BFS 특징 두 노드 사이의 최단 경로를 탐색할 때 활용하기 좋은 방식. 멀리 떨어진 노드는 나중에 탐색하기 때문이다. 큐를 활용해서 탐색할 노드의 순서를 저장하고 큐에 저장된 순서대로 탐색한다. 🔥 ..
✅ 트리(Tree)란? 부모와 자식 관계를 가진 노드로 구성된 데이터 구조이다. 리스트는 선형구조이다. 한 가지가 있고, 그다음에 하나 그다음에 하나 이런 식으로 모든 것이 한 줄로 늘어서 있다. 트리는 비선형구조로 여러 가지들로 뻗을 수 있다. 그리고 트리는 부모가 자식을 가리키는 형태이지 형제를 가리키거나 자식이 부모를 가리키면 안 된다. 루트(Root) - 트리의 최상위 노드. 자식(Child) - Root로부터 멀어지는 방향으로 다른 노드와 직접적으로 연결된 노드. 부모(Parent) - 자식의 반대 개념. 형제(Siblings) - 같은 부모를 가지는 노드들의 그룹이다. 리프(Leaf) - 자식이 없는 노드. 간선(Edge) - 한 노드에서 다른 노드로 향하는 화살표이다. 노드와 노드를 연결한다..
✅ 스택(Stack)이란? 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out, 후입선출)을 가진 자료구조이다. 스택은 가장 먼저 추가된 것이 가장 마지막에 제거되는 하나의 방식으로 그러한 구조를 만드는 방법은 여러 가지가 있다. 배열로 스택을 만든다고 가정하면, push와 pop메소드를 이용해 맨 마지막에 데이터를 삽입하고, 맨 마지막 데이터를 삭제하는 구조가 갖춰진다. unshift와 shift도 마찬가지이지만 비효율적이다. 그렇지만 사실 효율성만 따질 때는 배열을 스택으로 이용하지 않는 경우가 더 많다. 왜냐하면 인덱스 기반으로 정보에 접근할 필요가 없으니 인덱스들을 전부 다 가지고 있을 이유가 없다. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우..
