Algorithm/DS, algorithms

오일러 서킷

오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로 -> 한붓그리기 그래프의 시작점을 u, 끝점을 v라고 하자 1. u != v 인 경우 : v는 항상 홀수 개의 간선과 인접한다. v를 지나기 위해서 v로 들어가는데 하나, 나가는데 하나가 필요하다. 만약 v가 끝점이라면 v로 들어가는 간선에 대응하는 나가는 간선이 없다는 뜻이므로 v에 인접한 간선의 수가 홀수 일 수밖에 없다. 2. u == v 인 경우 : v는 항상 짝수 개의 간선과 인접한다. u에서 나가는 것으로 시작했기 때문에 u로 다시 들어왔다면 u(=v)에 인접하는 간선의 수는 짝수이다. 한 정점에 인접한 간선의 개수를 degree라고 하자. 오일러 서킷은 모든 정점에 들어가는 횟수와 나가는 횟수가 같아야하므로..

[자료구조] Single Linked List 예제 코드 #2 (C)

Single Linked List 구현하기 #2 따로 list의 크기를 입력받는 상황은 구현하지 않고 정적으로 이미 만들어진 노드에서 circular list로 만들고 검색하는 기능을 구현했다. 구현을 위한 메서드들 struct Node : list의 한 노드를 구성하는 구조체 struct Node* Create(int data) : list의 새 노드를 만드는 함수 struct Node* Insert(struct Node* current, int data) : current 라는 노드 뒤에(after라는 노드 앞에) 노드를 새로 만들고 data값을 설정 후 노드를 반환하는 함수 void destroy(struct Node* destroy, struct Node* head) : head 노드부터 탐색해서..

[자료구조] Single Linked List 예제 코드#1 (C)

Single Linked List 구현하기 #1 list의 크기를 입력받고 순서대로 value를 입력받아 동적할당 받은 list노드를 서로 연결해서 linked list로 만들어주었다. 구현을 위한 메서드들 typedef sturct _intlinked : list의 한 노드를 구성하는 구조체 il* make_node() : list의 헤더를 만드는 함수 void add_node(il* head, int value) : head 노드 뒤에 value값을 가진 노드를 연결해주는 함수 void destroyall(il* head) : head 노드부터 시작해서 list의 끝까지 메모리를 해제해주는 함수 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..

힙 정렬(heap sort) <priority queue> C++

min heap 구현 heap[i]의 값은 heap[i * 2] 와 heap[i*2 + 1]의 사이에 있다 BST(이진 탐색 트리)구조를 기반으로 한다 STL의 priority queue를 사용하면 되므로 직접 구현할 일은 없겠지만 heap 자료구조를 직접 구현해 본다는 점에서 의미있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include using namespace std; vector heap; void push_heap(vector& heap, int newvalue){ heap.push_back(newvalue); int idx = he..

Minimum Spanning Tree (MST) - Kruskal

크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인드(Union-Find)에 대한 이해 8할 Edge 구조체 설계 2할? find_topnode() 를 통해서 현재 정점(Vertax)의 최상단 노드(부모노드) 를 알 수 있다. Node[Vertax]의 값이 음수이면 Vertax가 부모노드임을 의미한다 is_cycle()을 통해서 a와 b 정점이 서로 같은 노드인지 확인한다(find_topnode() 사용) Union_node()를 통해서 a 와 b정점을 하나로 병합한다 a, b정점의 부모 노드가 가지는 값은 항상 음수이다. 값이 더 작을수록 더 많은..

Stack Permutation C++

순열을 구하기위해 dfs를 사용했는데 visit 배열 대신 stack을 사용해서 구현해보았음 n이 8이 넘어가면 하루종일 걸려요.. 모든 경우의 수를 출력해주기 때문에 어쩔 수 없다 if(node == N) 부분의 for 문을 보면 N이 i에 대한 조건으로 있는데 이 N을 입력받은 N보다 작게 바꿔주면 ex ) N이 6일 때 4로 설정 -> 6까지의 숫자 중 4개를 골라 만들 수 있는 모든 순열이 출력된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include using namespace std; vector _stack; int N, check[10] = {0, }; vo..

Union Find Basic Code C++

Union Find를 이해하기 위한 기본 코드 findTopnode를 통해서 최상단 노드를 알 수 있다 union_node를 통해서 입력된 수의 최상단노드를 찾아 두 수를 연결해주는 작업을 한다 check_node를 통해서 두 수가 서로 연결 되었는지 알 수 있다 www.cs.usfca.edu/~galles/visualization/DisjointSets.html Disjoint Sets Visualization www.cs.usfca.edu 위 사이트에서 눈으로 직접 보면서 이해할 수 있다!! 좋음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 4..