코딩뚠뚠

풀이일시 : 2020-08-30 ​ DFS : 깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다. 아래그림이 dfs를 한눈에 보여준다고 생각한다 출처 : http://www.aistudy.com/heuristic/depth-first_search.htm ​ 문제 : DFS를 구현하라 ​ 풀이 : recursive하게 구현한다. #include #include #define MAX 9 using namespace std; int d[MAX] = { 0, }; //방문체크하는배열 vector a[MAX]; void dfs(int x) { if (d[x] == 1) return; d[x] = true;//방문체크하기 cout

풀이 일시 : 2020-08-29 ​ 그리디알고리즘 : 당장 눈앞에의 최적의 상황만 쫓는 알고리즘이다. 대표적인 알고리즘으로는 가장 짧은 간선부터 연결하는 크루스칼 알고리즘이 있다. ​ 문제 : 총 몇개의 동전을 거슬러줘야되는가? => 최소값을 구하라 ​ 풀이 : 가장 큰 단위부터 거슬러줄 수 있다면 거슬러 주는 것이 동전을 가장 적게 사용하는 방법일 것이다. #include using namespace std; //총 몇개의 동전을 거슬러 줘야되는가 int main() { int n, result = 0; cin >> n; result += n / 500; n %= 500; //나머지 연산을 해서 다음 레이어로 간다. result += n / 100; n %= 100; result += n / 50; ..

풀이 일시 : 2020-08-22 ​ 라빈카프 알고리즘 : 문자열 매칭 알고리즘으로 해시기법을 이용한다. 충돌하는 경우에는 포인터를 이용해 연결자료구조(link)를 이용해 해결한다. ​ 문제 : 라빈카프 알고리즘을 이용하여 "ababacabacaabacaaba" 에서 "abacaaba"의 시작점을 찾아라 ​ 풀이 : #include #include using namespace std; void hashs(string parent, string pattern) { int parentHash=0, patternHash=0, power = 1; int parentSize = parent.size(); int patternSize = pattern.size(); for (int i = 0; i

풀이 일시 : 2020-08-21 ​ KMP알고리즘 : Knuth Morris Pratt 알고리즘 / 대표적인 문자열(string)매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘 ​ 문제1 : 일반 문자열 매칭 알고리즘 (KMP알고리즘 X) ​ 풀이 : BCDEF가 있고 그 중 DE를 찾을거면 자리를 하나씩 옮기며 비교하면서 매칭한다. O(N*M) #include using namespace std; int findString(string parent, string pattern) { int parentSize = parent.size(); int patternSize = pattern.size(); for (int i = 0; i ABCDABEDFS 에서 ABE를 찾고자..

풀이 일시 : 2020-08-21 ​ 이분매칭 : A집단이 B집단을 선택하는 방법에 대한 알고리즘 효과적으로 집단을 매칭해준다. (최대매칭) ​ 문제 : 연결될 수 있는 쌍을 나타내고 그 중 최대 매칭을 계산 후 매칭 된 것을 나타내자 ​ 풀이 : DFS로 풀이 가능 dbstndi6316.tistory.com/64?category=953968 [기본문제풀이] DFS 깊이우선탐색 풀이일시 : 2020-08-30 ​ DFS : 깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다. 아래그림이 dfs를 한눈에 보여준다고 생각한다 출처 : http:// dbstndi6316.tistory.com #include #include #define MAX 101 ..

풀이 일시 : 2020-08-17 ​ 강한결합요소 : strongly connected component SCC로 부르기도 한다. 같은 SCC에 속하는 두 정점은 서로 도달이 가능하다. ​ 문제 : SCC의 갯수와 각 SCC에 담긴 인자들을 출력하라 ​ 풀이 : 모든 정점에 대해 DFS를 수행해서 SCC를 찾는 알고리즘으로 풀이한다. 1->2->3->4 에서 다시 1로 돌아갈 수 있어야 SCC가 성립하는 것. ​ #include #include #include #include #define MAX 10001 using namespace std; int id, d[MAX]; bool finished[MAX]; //특정한 dfs가 끝났는지 확인하기위해 vector a[MAX]; vectorSCC; stack..

풀이 일시 : 2020-08-16 ​ 위상정렬 : 순서가 정해져 있는 작업을 차례로 수행해야 할 때 순서를 결정하기 위해 큐 사용 ​ 문제 : topology sort 수행 ​ 시간복잡도 : O(V+E) ​ 풀이 : #include #include #include #define MAX 10 using namespace std; int n, inDegree[MAX]; vector a[MAX]; void topologySort() { int result[MAX]; queue q; for (int i = 1; i

풀이 일시 : 2020-08-13 ​ 플로이드와샬 알고리즘 : 그래프 정점간 최단거리를 구하는 알고리즘 중 모든 최단 경로를 구하는 방법이다. (다익스트라는 한 점에서 다른점까지의 최단 경로) 또한 플로이드와샬에서는 음의 가중치를 가진 간선을 사용할 수 있다. 모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 된다. ​ 문제 : 주어진 인접행렬에서 플로이드 와샬 알고리즘을 사용하여 모든 거리를 구하라 {0 , 5 , inf , 8}, {7 , 0 , 9 , inf}, {2 , inf , 0 , 4}, {inf , inf , 3 , 0} 풀이 : #include int number = 4; int inf = 10000000; int a[4][4] = { {0,5,inf,8}, {7..