코딩뚠뚠

풀이 일시 : 2020-08-17 ​ 네트워크 플로우 : 특정한 지점에서 다른 지점으로 데이터가 얼마나 흐르는가를 따지는 것 유량/ 용량 으로 용량보다 더 많이 보낼수는 없다. BFS를 이용해서 단순히 모든 경우의 수를 탐색해주자 1. 현재 흐르는 유량을 0으로 초기화 2. 정해진 용량안에서 가능한!! 최대 용량의 양을 반복적으로 더해준다. 3. 음의 유량을 계산해준다. (반대로 가는 유량) -> 빼준다면 다른것이 그 길로 또 갈수 있기 때문 (남은 경로를 더 찾을 수도 있다.) ​ 문제 : 음의 유량 따져서 최대 유량을 구하라 풀이 : #include #include #include #include #define MAX 100 #define INF 1000000000 using namespace std..

풀이 일시 : 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..

풀이 일시 : 2020-08-13 ​ 다익스트라 알고리즘 : 최단경로를 탐색하는 알고리즘이다. GPS등에 사용됨 음의간선이 존재하지 않는다. 최단거리는 여러개의 최단거리로 이루어져있다. 탐색하면서 최소비용인 것으로 갱신해나간다. ​ 문제 : 주어진 weight table을 보고 start 에서부터 최소비용을 추출하라 ​ 풀이1 : 선형탐색방법으로 구현 O(N^2) #include int number = 6; int INF = 10000000; int a[6][6] = { //weight table {0,2,5,1,INF,INF}, {2,0,3,2,INF,INF}, {5,3,0,3,1,5}, {1,2,3,0,1,INF}, {INF,INF,1,1,0,2}, {INF,INF,5,INF,2,0} }; bool ..

풀이 일시 : 2020-08-13 ​ 에라토스테네스의 체 : 소수(prime number) 판별 알고리즘이다. 어떤 수로도 나뉘어지지 않아야 되기 때문에 그 수를 나눠보면서 판단할 수 있다.. -> 이 방법은 O(N)의 복잡도를 갖는다. 모든 수를 체크했기 때문이다. 제곱근까지만 약수의 여부를 검증한다 -> 이 방법은 O(N^(1/2))로 계산이 가능하다. -> int end = (int)sqrt(x)로 두고 x의 소수를 구하려면 2~end까지 체크한다. ​ 문제 : 에라토스테네스의 체를 이용하여 소수를 출력하여라. ​ 풀이 : 1. 이차원 배열을 생성하여 값을 초기화한다. 2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다. (자신은 지우지않는다.) 3. 3의 배수도 지운다. (자신..

풀이 일시 : 2020-08-08 ​ 다이나믹프로그래밍 : 하나의 문제는 단 한번만 풀도록 하는 알고리즘으로 효율성을 개선하는 알고리즘이다. 가정1 - 큰 문제를 작은 문제로 나눌 수 있다. 가정2 - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 작동한다. 이미 계산한 결과는 배열에 저장함으로써 나중에 꺼내서 쓰기만 하면 되게끔 한다. ​ 문제 : dp로 피보나치 구현 풀이 : #include int d[100] = { 0, }; //배열 선언 및 전체 0으로초기화 int fibonacci(int x) { if (x == 1) return 1; //1과 2는 피보나치에서 뭘 더해서 나오는 수가 아니기때문에 거른다 if (x == 2) return 1; if (d[x] != 0){ return..

풀이 일시 : 2020-08-08 ​ Traversal : '순회' 라는 뜻이다. 이진트리의 순회를 재귀호출로 구현할 수 있다. 이진트리의 구현과 순회방식 : 가장 많이 사용되는 비선형 자료구조는 이진트리이고 이는 데이터의 탐색속도 증진을 위해 사용된다. 실제로 트리를 제대로 구현하기 위해서는 포인터를 사용해야한다. 왜냐하면 완전 이진트리가 아닌것은 배열로 표현하기가 어렵기 때문이다. ​ 전위순회 : V L R 중위순회 : L V R 후위순회 : L R V ​ #define number 15 #include using namespace std; //class : 접근제어자 기본 private //구조체 : 접근제어자 기본 public //구조체를 포인터형태로 사용하기위해 , 노드 구조체를 treePoin..