algorithm 🔑
-
최단거리구하기_다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘에 대한 이해 - 하나의 정점으로 부터 다른 모든 정점까지의 최단거리를 구하는 문제이다. - 음수 간선이 있는 그래프에서는 사용할 수 없다. - 우선순위큐를 이용한다. V = 6, E = 7인 다음 그래프에 대하여, 정점 1번으로 부터 다른 모든 정점까지의 거리를 구해보자. 1번으로부터의 거리를 저장하는 dist 배열을 구성하고, 우선순위 큐에 1번 노드의 (거리, 노드번호)를 추가한다. 우선순위 큐는 가장 작은 값을 먼저 뱉어내므로, 1번으로부터의 거리가 가장 가까운 노드를 뽑아내면 (0, 1)이 된다. 이 때, 큐에서 뽑아낸 (0, 1)의 정보와 배열의 정보 dist[1] = 0이 일치하므로 1번까지의 거리를 확정한다. 1번에서 이동할 수 있는 노드는 2번 노드 뿐이다. 거리가 확정..
2022.08.29
-
비트 연산_AND 연산/OR 연산/ XOR 연산/ NOT 연산 / Shift 연산 / 비트의 특정 인덱스 추출(업데이트)
비트 연산 0과 1로 이루어진 이진수의 비트 별 연산 AND 연산(&) 두 비트가 모두 1일 때만 1인 연산 0 0 1 1 0 1 0 1 -------- 0 0 0 1 OR 연산(|) 두 비트 중 하나라도 1이면 1인 연산 0 0 1 1 0 1 0 1 -------- 0 1 1 1 XOR 연산(^) 두 비트가 다르면 1인 연산 1 1 0 1 0 1 0 1 -------- 1 0 0 0 NOT 연산(~) 0을 1로, 1을 0으로 변환하는 연산 0 1 0 1 -------- 1 0 1 0 Shift 연산 - Left shift: 비트들을 왼쪽으로 k칸씩 옮기고 남는 자리에 0을 채우는 연산 (x > k) 1 0 0 1 > 2 --------------- 1 0 특정 인덱스의 값을 추출하는 법 num = 12..
2022.04.03
-
완전탐색_순열/중복순열/조합/중복조합
순열(Permutation) - n개 중 r개를 선택할 때, 순서를 고려하고 중복을 허용하지 않는 방법 - nPr = n!/(n-r)! - 재귀적으로 배열을 채워나가면서 중복하는 숫자가 없도록 check 배열을 업데이트 #include #include using namespace std; //순열: 순서 O, 중복 X //nPr = n!/(n-r)! #define n 3 #define r 2 int arr[30]; int check[30]; void printarr() { for (int i=0; i
2022.03.11
-
최단거리구하기_플로이드 와샬(Floyd Warshall) 알고리즘
플로이드 알고리즘에 대한 이해 - 플로이드 알고리즘이란, 그래프의 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이다. - 모든 정점 쌍에 대한 2차원 표를 채우는 과정으로 진행된다. V(노드의 개수) = 6, E(간선의 개수) = 7 인 다음과 같은 그래프에서 모든 정점 쌍 사이의 최단 거리를 구해보자. 먼저, 아무 정점도 거치지 않았을 때 정점 i와 정점 j 사이의 최단 거리로 표를 채운다. 예를 들어, 정점 3과 정점 6은 아무 정점도 거치지 않았을 때 거리가 8이다. 물론, 3 -> 2 -> 5 -> 6 으로 이동하는 경우 더 작은 거리(7)로 도달할 수 있으나, 가장 처음에는 다른 정점을 거치는 경우를 제외하고 직행으로 연결하였을 때의 최단 거리만 표에 기록한다. int V, E; vector..
2022.03.07
-
최소신장트리(Minimal Spanning Tree)_크루스칼(Kruscal) 알고리즘
최소신장트리(MST)에 대한 이해 - 신장트리란, 뱡향성이 없는 그래프의 부분그래프(Subgraph)들 중에서, 모든 정점을 포함하는 트리이다. - 최소신장트리란, 신장트리들 중에서 간선의 합이 가장 작은 트리를 말한다. - 그래프에서 최소신장트리는 여러 개 있을 수 있다. 최소신장트리를 구하는 알고리즘으로는 크게 크루스칼(Kruscal) 알고리즘과 프림(Prim) 알고리즘이 있으며, 해당 글에서는 크루스칼 알고리즘의 방법을 다룬다. V(노드의 개수) = 6, E(간선의 개수) = 7 인 다음과 같은 그래프에서 최소신장트리의 간선 길이의 합을 구해보자. 간선들 중, 가장 길이가 짧은 간선을 선택하여 연결된 두 노드를 확인한다. 만약 두 노드가 다른 집합에 속해있다면 두 노드를 같은 집합에 포함시키고 해당..
2022.03.04