본문 바로가기

ㄴ 알고리즘/테크닉19

최단거리구하기_다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘에 대한 이해 - 하나의 정점으로 부터 다른 모든 정점까지의 최단거리를 구하는 문제이다. - 음수 간선이 있는 그래프에서는 사용할 수 없다. - 우선순위큐를 이용한다. V = 6, E = 7인 다음 그래프에 대하여, 정점 1번으로 부터 다른 모든 정점까지의 거리를 구해보자. 1번으로부터의 거리를 저장하는 dist 배열을 구성하고, 우선순위 큐에 1번 노드의 (거리, 노드번호)를 추가한다. 우선순위 큐는 가장 작은 값을 먼저 뱉어내므로, 1번으로부터의 거리가 가장 가까운 노드를 뽑아내면 (0, 1)이 된다. 이 때, 큐에서 뽑아낸 (0, 1)의 정보와 배열의 정보 dist[1] = 0이 일치하므로 1번까지의 거리를 확정한다. 1번에서 이동할 수 있는 노드는 2번 노드 뿐이다. 거리가 확정.. 2022. 8. 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. 4. 3.
완전탐색_순열/중복순열/조합/중복조합 순열(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. 3. 11.
최단거리구하기_플로이드 와샬(Floyd Warshall) 알고리즘 플로이드 알고리즘에 대한 이해 - 플로이드 알고리즘이란, 그래프의 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이다. - 모든 정점 쌍에 대한 2차원 표를 채우는 과정으로 진행된다. V(노드의 개수) = 6, E(간선의 개수) = 7 인 다음과 같은 그래프에서 모든 정점 쌍 사이의 최단 거리를 구해보자. 먼저, 아무 정점도 거치지 않았을 때 정점 i와 정점 j 사이의 최단 거리로 표를 채운다. 예를 들어, 정점 3과 정점 6은 아무 정점도 거치지 않았을 때 거리가 8이다. 물론, 3 -> 2 -> 5 -> 6 으로 이동하는 경우 더 작은 거리(7)로 도달할 수 있으나, 가장 처음에는 다른 정점을 거치는 경우를 제외하고 직행으로 연결하였을 때의 최단 거리만 표에 기록한다. int V, E; vector.. 2022. 3. 7.
최소신장트리(Minimal Spanning Tree)_크루스칼(Kruscal) 알고리즘 최소신장트리(MST)에 대한 이해 - 신장트리란, 뱡향성이 없는 그래프의 부분그래프(Subgraph)들 중에서, 모든 정점을 포함하는 트리이다. - 최소신장트리란, 신장트리들 중에서 간선의 합이 가장 작은 트리를 말한다. - 그래프에서 최소신장트리는 여러 개 있을 수 있다. 최소신장트리를 구하는 알고리즘으로는 크게 크루스칼(Kruscal) 알고리즘과 프림(Prim) 알고리즘이 있으며, 해당 글에서는 크루스칼 알고리즘의 방법을 다룬다. V(노드의 개수) = 6, E(간선의 개수) = 7 인 다음과 같은 그래프에서 최소신장트리의 간선 길이의 합을 구해보자. 간선들 중, 가장 길이가 짧은 간선을 선택하여 연결된 두 노드를 확인한다. 만약 두 노드가 다른 집합에 속해있다면 두 노드를 같은 집합에 포함시키고 해당.. 2022. 3. 4.
유니온파인드(Union-Find) Union-Find 에 대한 이해 - 공통 원소가 없는, "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. - 원소들이 어떠한 집합에 포함되어있을 때, 특정 원소가 포함되어있는 집합을 찾는 Find 연산을 지원한다. - 두 원소들이 속한 집합이 다를 때, 두 집합을 하나의 집합으로 합치는 Union 연산을 지원한다. 트리 형태로 표현되어있는 원소들간의 서로소 집합을 살펴보자. 위의 그림에서 원소들의 상호 배타적 집합은 총 4개이다. 각 원소들은 하나의 집합에 포함되어있고, 같은 집합에 포함되어있는 원소들은 같은 루트 노드를 공유한다. 예를 들어, 노드 2번과 노드 4번은 같은 집합에 포함되어 하나의 트리로 연결되어있고 루트 노드 1번을 공유한다. 노드 6번과 노.. 2022. 3. 3.
위상정렬(Topological sort) 위상정렬 - 위상정렬이란, 사이클이 없는 방향 그래프(DAG: Directed Acyclic Graph)에서 정점 사이의 선후 관계를 위배하지 않고 정렬하는 알고리즘이다. - 흔히 선수과목들의 수강 순서를 정하는 문제가 위상정렬에 비유된다. - 정해진 순서를 위배하지 않고 정렬하는 방법은 여러가지가 있을 수 있다. 위상정렬의 과정 N(노드의 개수) = 7, M(간선의 개수) = 7 인 다음과 같은 그래프에서 위상정렬을 수행해보자. 간선이 노드 x에서 노드 y로 흐를 때, 노드 x는 노드 y보다 앞에 위치되어야 한다. - 즉, 어떠한 노드가 해당 노드 쪽으로 들어오는 간선을 가지고 있다면 이 노드는 가장 앞에 올 수 없다. - 결과적으로, 현재 상태에서 가장 앞에 올 수 있는 노드들은 indegree(노드.. 2022. 3. 1.
트리_그래프가 트리인지 확인하는 방법 그래프가 트리인지 확인하는 방법 - 트리는 노드 N개, 간선 N-1개를 가지면서 사이클이 없는 특징을 가진다. - 따라서 사이클이 있다면(탐색하는 과정에서 부모 이외의 이전에 방문했던 노드를 또 방문하게 된다면) 이는 트리가 아닌 그래프이다. #include #include #include using namespace std; int N, M; vector graph(15, vector(0)); vector visited(15, false); vector parent(15, 0); void setGraph() { scanf("%d %d", &N, &M); for (int i=0; i 2022. 2. 28.
이진트리순회_레벨순회(level)/전위순회(preorder)/중위순회(inorder)/후위순회(postorder) 트리 자료구조란 - 무방향이면서 사이클이 없는 연결그래프(즉, 트리는 그래프의 일종) - N개의 노드와 N-1개의 간선을 가짐 - 이진트리란, 트리 중 각 노드의 자식들이 2개 이하인 트리 - 이진트리를 순회하는 방식은 크게 레벨순회, 전위순회, 중위순회, 후위순회가 있음 레벨 순회(Level Order Traversal) - 트리의 루트부터 리프까지 계층적으로 순회하는 방식 - 가장 높은 층을 먼저 순회하며 큐로 구현 - 그래프에서의 bfs와 동일하게 구현하나, 사이클이 없기 때문에 이전에 방문한 노드를 별도로 체크해줄 필요가 없음(부모 노드만 기록) #include #include #include using namespace std; int N; vector graph(10, vector(0)); v.. 2022. 2. 27.
가장긴증가하는부분수열(LIS)_DP/Binary Search 가장 긴 증가하는 부분수열의 개념 부분 수열이란, 본래 수열에서 일부 숫자를 지워 만들 수 있는 수열이다. 가장 긴 증가하는 부분 수열(LIS, Logest Increasing Subsequence)은 오름차순으로 증가하는 부분 수열 중에서 가장 긴(원소의 개수가 많은) 수열을 의미한다. 예를 들어, N = 7인 수열 {6, 2, 4, 3, 1, 4, 8}은 여러 부분 수열을 가진다. - {6, 4, 1}, {6, 8}, {3, 4}, {2, 3, 4} 등은 모두 부분수열이다. - 그 중에서 {2, 4, 8}, {4, 8}, {2, 3, 4}, {1, 4, 8} 등은 증가하는 부분 수열이다. - 가장 긴 증가하는 부분 수열은 길이가 4인 {2, 3, 4, 8} 이다. 가장 긴 증가하는 부분 수열의 길이는.. 2022. 2. 20.

티스토리툴바