:)

📖 벨만포드(Bellman-Ford) 알고리즘벨만포드(Bellman-Ford) 알고리즘이란?: 최단 경로(shortest path)를 찾는 알고리즘 중 하나다익스트라(Dijkstra) 알고리즘과 차이점: 다익스트라는 음의 가중치가 있는 그래프에서 작동하지 않으며 벨만포드는 이러한 그래프에서 작동한다.: 벨만포드는 다익스트라보다 단순하며 분산 시스템에 적합하다.: 다익스트라 알고리즘은 Greedy 알고리즘이며 시간 복잡도는 O((V+E)LogV)이다. 벨만포드의 시간 복잡도는 O(V * E)로 다익스트라보다 더 크다.벨만포드 알고리즘 예시↓위에 제시된 예시의 벨만포드 알고리즘 과정을 그림으로 표현↓벨만포드 알고리즘 코드#include using namespace std;struct Edge { int ..

📖 그래프 표현 방법그래프 표현 방법으로는 인접 행렬과 인접 리스트가 존재한다.인접 행렬(예시)(코드)-그래프 형태는 무방향 그래프라고 가정한다.#includeusing namespace std;int vertArr[20][20];int count = 0;void displayMatrix(int v) { int i, j; for(i = 0; i 인접 리스트(예시)(코드)-그래프 형태는 무방향 그래프라고 가정한다.#include#include#includeusing namespace std;void displayAdjList(list adj_list[], int v) { for(int i = 0; i "; list :: iterator it; for(it = adj_list[i]...

📖 그래프정의: Vertices와 Edges로 구성된 비선형 데이터 구조: 그래프(G)는 정점(V)와 간선(E)로 표현 -> G=(V,E)관련 용어정점(또는 노드)여러 가지 특성을 가질 수 있는 객체V(G) : 그래프 G의 정점들의 집합간선(또는 링크)- 정점들 간의 관계- E(G) : 그래프 G의 간선들의 집합📖 그래프 탐색 과정그래프 탐색: 하나의 정점에서 시작하여 모든 정점들을 차례대로 한번씩 방문하는 것그래프 탐색 과정은 BFS와 DFS 알고리즘을 바탕으로 이루어진다.📍 BFS (Breadth-First Search)정의 : 너비 우선 탐색아래 예시로 제시된 그래프를 활용한 탐색 과정은 다음과 같다.(예시)(탐색 과정)-> b부터 탐색 시작-> d와 a 방문 (이때 d,a는 큐로 enqueu..

📖 Data structures augmentation데이터 구조가 효율적으로 구현될 수 있도록 기존 데이터 구조에 추가 정보 추가하는 것이진 탐색 트리 노드에 서브 트리 노드 개수 정보 추가: root에서 내려와 해당 value보다 작거나 같으면 1을 더하고 왼쪽에 있는 서브 트리 개수를 더해준다.📖 Rank이진 탐색 트리에서 노드의 Rank는 왼쪽 서브트리의 노드 수가 중요하다.-코드int getRank(Node* root, int x){ if (root->data == x) return root->leftSize; if (x data) { if (!root->left) return -1; else retur..

📖스케줄링 문제에 접근하는 이진 탐색 트리정의 : 이진트리 기반의 탐색을 위한 자료구조이진트리 : 모든 노드가 2개의 subtree를 갖는 트리모든 노드의 차수는 2 이하 -> 최대 2개까지의 자식노드를 가질 수 있다left subtree와 right subtree는 반드시 구별되어야 한다탐색 : 컴퓨터, 자료구조에서의 핵심적인 응용 분야특징nearly complete X왼쪽 노드 키 각각의 노드가 2개이하의 노드를 갖고 있어야한다모든 노드 x에 대해 if y가 x의 left subtree에 있다면 key(y) if y가 right subtree에 있다면 key(y) >= key(x)balanced가 되기 위해서는 left(h)와 right(h)가 비슷해야한다연산insert(n): 이진 탐색 트리의 특..

📖우선순위큐와 힙 내용 정리우선순위 큐와 힙이 같은 개념이라고 오해할 수 있지만 둘은 서로 다른 개념이다. 우선순위 큐와 힙에 대해 알아보기 전, 이를 이해하기 위해 알아둬야할 개념은 다음과 같다. * 큐 : 먼저 들어온 데이터가 먼저 나가는 형식(First In First Out)의 자료구조이다. * 완전이진트리 : 왼쪽부터가 오른쪽으로 노드가 채워지는 형식이며, 마지막 레벨을 제외한 모든 레벨이 채워져 있는 형태이다.'우선순위 큐'의 특징-일반적인 큐와 다르게 우선순위의 개념을 큐에 적용한 자료구조-들어간 순서에 상관 없이 우선순위를 근거로 dequeue 연산이 진행된다.-두 요소의 우선 순위가 동일한 경우 대기열에서 해당 요소의 순서에 따라 진행된다.'힙'의 특징-완전 이진 트리-최대 힙: 모든 ..