분류 전체보기 (37) 썸네일형 리스트형 최소 비용 신장 트리 (Minimum cost Spanning Tree; MST) 단순 경로 (Simple path)와 사이클 (Cycle) 단순 경로 (Simple path) : 경로 중 간선이 중복되지 않을 시 단순 경로라고 불립니다. (ex. A-D-B-C, A-D-B-D-A-C는 A와 D를 잇는 간선이 중복되어 단순 경로가 될 수 없습니다.) 사이클 : 단순 경로이면서 시작 정점과 끝 정점이 같은 경로 최소 비용 신장 트리 (Minimum cost Spanning Tree; MST) 최소 비용 트리(MST)는 아래 2가지 조건을 충족해야합니다. 모든 정점이 하나의 간선으로 연결되어야 합니다. 사이클이 형성되지 않아야 합니다. MST는 간선의 수가 정점의 수보다 하나 적다는 특징이 있습니다. (간선의 수 + 1 = 정점의 수) MST를 구성하는 알고리즘은 크루스칼(kruskal).. DFS (깊이 우선 탐색) | BFS (너비 우선 탐색) 깊이 우선 탐색 (DFS; Depth First Search) DFS는 아래 조건 3가지를 충족하는 그래프 탐색 방법입니다. 정점를 하나씩 탐색한다. 탐색할 정점이 없을 시 그 전 노드를 탐색한다. 처음 탐색한 정점에서 탐색이 종료된다. DFS 탐색 구현 #pragma once #include #include #include #include using namespace std; class graph { private: vector *pgraph = nullptr; int count_edge = 0; public: graph() = delete; graph(int vertex) { pgraph = new vector[vertex]; } ~graph() { delete[] pgraph; } void add(.. 그래프 (Graph) 구조 그래프는 정점(vertex)과 간선(edge)으로 이루어진 구조입니다. 이는 지하철의 노선도와 비슷한 개념이기도 합니다. 지하철의 노선도처럼 정점과 정점사이의 최적의 경로를 알 수도 있습니다. 종류 방향 그래프 (directed graph); 다이그래프 (digraph) 방향에 대한 정보가 그려진 그래프입니다. 이와 반대로 방향이 없는 무방향 그래프(undirected graph)가 있습니다. 완전 그래프 (complete graph) 모든 정점이 자신을 제외한 모든 정점을 연결한 그래프입니다. 방향 그래프는 모든 정점을 가리켜야하므로 두 정점당 2개의 간선이 나타납니다. 가중치 그래프 (weight graph) 간선에 가중치에 대한 정보를 표시하여 구성한 그래프입니다. 가중치의 의미는 이동시간으로.. 테이블 (Table) : 체이닝 (Chaining) 원리 닫힌 어드레싱 방법(closed addressing mehod), 즉 어떤 상황이든지 충돌이 발생해도 자신에 맞는 자리에 저장하는 방식인 테이블입니다. 이 방법은 자신의 자리에 저장해야하므로, 2차원 배열이나 연결리스트를 배열로 할당하는 방식이 있습니다. C++에서는 list stl이 제공되므로 list를 동적할당하여 구현할 수 있습니다. 2차원 배열보다 연결 리스트를 사용하는 이유는 배열의 특성으로 인해 자원 낭비가 매우 심할 가능성이 존재하고, 연결 리스트는 길이에 가변성이 있기 때문입니다. 소스 코드 (구현) Node.h #pragma once #include #include using namespace std; template class Node { template friend class t.. 테이블 (Table) : Key & Value, Hash (해쉬), Collision (충돌) 원리 테이블(Table)의 기본 원리는 "중복되지 않는 Key(키)와 Key(키)와 한 쌍을 이루는 Value(값)이 존재해야 한다."입니다. 즉, 모든 Key(키)는 중복되지 않으면서, 모든 Value는 하나의 Key(키)와 한 쌍을 이루어야 합니다. 이러한 원리 덕분에 테이블은 \(O(1)\)이라는 압도적인 성능을 가집니다. 테이블은 이런 특성 때문에 dictionary(사전) 또는 map(맵)이라고 불리기도 합니다. 해쉬 (hash) 데이터를 저장하다보면 Key(키)의 범위가 매우 많아져 인덱스 값이 커지는 경우가 발생합니다. 이를 대비하여 만들어진 것이 바로 해쉬 함수 (hash function)입니다. 예를 들어 8자리의 학번을 배열에 저장할 시, 해쉬 함수를 적용하지 않을 경우 최대 10000.. 탐색 (Search) : AVL 트리 (AVL Tree) 원리 이진 트리 탐색 (Binary Search Tree)는 최악의 경우 \(O(n)\)이라는 시간 복잡도를 가집니다. 이를 대비하여 트리를 꾸준하게 리밸런싱(Rebalancing)을 해줘야하고, 그로 인해 나온 트리 중 하나가 AVL Tree입니다. 균형 인수 : 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 리밸런싱을 진행할 시 균형인수의 절댓값이 2이상이여야 합니다. LL 회전 왼쪽에 노드가 2개 이상, 즉 균형 인수가 2이상인 경우 LL회전을 통해 균형을 잡습니다. RR 회전 오른쪽에 노드가 2개 이상, 즉 균형 인수가 -2이하인 경우 RR회전을 통해 균형을 잡습니다. LR 회전 왼쪽에 자식 노드가 존재하고 그 자식 노드의 오른쪽에 자식 노드가 존재하는 서브트리, 즉 균형 인수가 왼쪽 서브트.. 백준 11866 : 요세푸스 문제 0 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 N과 K를 입력한 후, 1부터 N까지의 수 중 K번째인 수를 제거한 후 나머지 수도 반복하여 제거된 순서를 출력하는 문제입니다. 풀이 C++ stl에 있는 queue를 사용했습니다. K번째 수가 아니면 앞에 있는 수를 push한 후 pop을 합니다. K번째 수이면, 숫자를 출력한 후 pop을 진행합니다. 출력 양식을 맞추기 위해 숫자 출력과 pop을 한 후에 queue가 비어있으면 ","을 출력하지 않았습니다. 소스 코드 #include #include using namespace std; int main() { queue q; int N, K; scanf("%d%d", &N, &K); for (int i = 1; i 백준 2164 : 카드2 [C++] 문제 문제에 대한 링크는 여기를 클릭해주세요. 문제 설명 N을 입력한 후 1부터 N까지의 숫자가 써있는 카드를 가지고 맨 위 카드를 버린뒤 그 다음 맨위의 카드는 맨 아래로 이동하는 행위를 반복합니다. 이후 마지막에 남은 카드를 출력하는 문제입니다. 풀이 C++ STL에 있는 queue를 사용하였습니다. for문을 사용하여 queue의 size가 1이 될때까지 반복하였습니다. queue를 pop함으로써 카드를 버리고 front의 있는 값을 push하고 pop을 함으로써 맨 뒤로 이동시켰습니다. 소스 코드 #include #include using namespace std; int main() { queue q; int N; scanf("%d", &N); for (int i = 1; i 이전 1 2 3 4 5 다음
