본문 바로가기

알고리즘 문제풀이/기본문제풀이26

[기본문제풀이] 강한결합요소 풀이 일시 : 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. 12. 28.

[기본문제풀이] topology_sort 풀이 일시 : 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. 12. 28.

[기본문제풀이] floydwarshall 풀이 일시 : 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. 12. 28.

[기본문제풀이] dijkstra algorithm 풀이 일시 : 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. 12. 28.

[기본문제풀이] 에라토스테네스의 체 풀이 일시 : 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. 12. 28.

[기본문제풀이] dynamic_programming 풀이 일시 : 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. 12. 28.

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

[기본문제풀이] union_find 풀이 일시 : 2020-08-06 합집합찾기 : 대표적인 그래프알고리즘이며 서로소집합 알고리즘이라고도 한다. 여러개의 노드가 존재할 때 두개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 문제 : union find로 연결여부를 판단한다. 풀이 : 연결되어있다면 같은 부모를 갖게끔 초기화 해준다. 소속을 같게 해준다. #include int getParent(int parent[], int x) { //핵심 재귀알고리즘 if (parent[x] == x) return x; return parent[x] = getParent(parent, parent[x]); //계속 찾아들어간다 } void unionParent(int parent[], int a, .. 2020. 12. 28.

이전 1 2 3 4 다음

티스토리툴바