Programming/알고리즘
-
위상 정렬(Topology sort)Programming/알고리즘 2020. 11. 17. 15:36
위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 위와 같은 경우 필요한 절차를 순서대로 밟아야 가능한 경우이며 이럴 때 사용되는 정렬이 위상 정렬이다. 위상 정렬 : 대학생 되기 -> 교수님 컨펌 -> 주제 선정 -> 개발하기 -> 졸작 완성 -> 졸작 전시 -> 졸업 ▷위상 정렬은 시작점을 알아야하기 때문에 위와 같이 사이클이 형성된 그래프에는 위상 정렬을 적용할 수 없다. 대학생의 졸업 과정을 번호를 부여하여 그래프로 나타내면 위상 정렬을 구현하는데 벡터와 큐를 사용하였다. 차수를 나타내는 배열을 선언하여 차수가 0인 것을 우선 전부 큐에 넣고 각 노드마다 인접 노드를 방문하며 차수를 1씩 감소시키며 큐가 빌 때까지 반복문을 사용하였다. ..
-
플로이드 와샬 알고리즘Programming/알고리즘 2020. 11. 16. 18:19
다익스트라 알고리즘은 한 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘인데 반해 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 최소의 비용을 가지는 간선을 선택하였다면, 플로이드 와샬 알고리즘은 특정 노드를 거쳐가는 경로에 대한 알고리즘이다. 그래프가 위와 같이 형성되었다고 가정하면 소스코드는 #include #define INF 1e9 using namespace std; int number = 4; int a[4][4] = { {0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF, 0, 4}, {INF, INF, 3, 0} }; void floyd() { int result[4][4]; // 결과값을 담는 배열 ..
-
다익스트라(Dijkstra) 알고리즘Programming/알고리즘 2020. 11. 16. 02:08
다익스트라(Dijkstra) 알고리즘은 다니아닉 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다(이때 음의 간선은 포함될 수 없다). 현실세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라 알고리즘은 현실 세계에서 적용하기에 매우 적합한 알고리즘이라고 할 수 있다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져있기 때문이다.' --> 현재까지 알고 있던 최단 경로를 계속해서 갱신한다! 이번 게시물에서의 그래프 예시는 위와 같이 정했다. 먼저, 배열을 사용해서 다익스트라 알고리즘을 완성해보자. #include using namespace std; ..
-
에라토스테네스의 체Programming/알고리즘 2020. 11. 15. 13:01
에라토스테네스의 체는 대표적인 소수(Prime Number) 판별 알고리즘이다. 에라토스테네스의 체 알고리즘은 한 두개의 소수를 판별하는 경우가 아닌 대량의 소수를 한꺼번에 판별할 때 사용한다. 에라토스테네스의 체는 우선 예를 들어 1부터 100까지의 수에서 소수를 판별한다고 하면 크기가 101인 int형 배열을 선언한다. 그리고 초기에 각 인덱스는 인덱스의 값으로 초기화를 시켜준다. 그 후 반복문을 통해 2의 배수, 3의 배수 ,4의 배수, ... 에 해당하는 인덱스의 값을 0으로 바꿔주는데 시간 복잡도를 줄이기 위해 이미 0인 부분은 continue를 사용하여 스킵되도록 한다. #include using namespace std; int number = 100; int a[101]; void isPr..
-
다이나믹 프로그래밍 (Dynamic Programming)Programming/알고리즘 2020. 11. 7. 21:10
다이나믹 프로그래밍이란 '하나의 문제는 한번만 풀게 하는 알고리즘'이다. 즉, 이미 해결한 문제를 중복적으로 수행하는 것을 방지하는 알고리즘이다. 일반적으로 대부분의 분할 정복 기법은 동일한 문제를 다시 풀게 된다는 단점이 있다. (정렬과 같은 경우는 이러한 문제가 일어나지 않는다. 그 예시로 퀵 정렬과 병합 정렬은 매우 빠르게 정렬을 수행할 수 있다.) 분할 정복 기법의 단점이 드러나는 대표적인 예로는 '피보나치 수'가 있다. *피보나치 수열의 점화식 : D[i] = D[i-1] + D[i-2] 만약 15번째 피보나치 수를 구하고자 한다면 14번째 피보나치 수와 13번째 피보나치 수를 더해야 한다. 그럴 경우, 14번째 피보나치 수를 또 구해야 하는데 이 과정에서 이미 구한 13번째 피보나치 수를 구하..
-
이진 트리와 순회 방식Programming/알고리즘 2020. 11. 7. 20:14
이진 트리는 가장 많이 사용되는 비선형 자료구조다. 이진 트리를 사용하는 목적은 데이터의 탐색 속도의 증진을 위해 사용하는 것이다. 트리를 구현할 때는 배열이 아닌 포인터를 사용한다. ▷왜 포인터를 사용할까? ▶힙 정렬을 구현할 때는 완전 이진 트리 형식이기에 배열로 표현할 수 있었으나, 완전 이진 트리가 아닌 이진 트리는 배열로 구현하기 힘들기에 포인터를 사용하여 왼쪽 자식과 오른쪽 자식을 나타낸다! 1. 전위 순회(Preorder traversal) 1) 자기 자신을 처리한다. 2) 왼쪽 자식을 방문한다. 3) 오른쪽 자식을 방문한다. 2. 중위 순회(Inorder traversal) 1) 왼쪽 자식을 방문한다. 2) 자기 자신을 처리한다. 3) 오른쪽 자식을 방문한다. 3. 후위 순회(Postord..
-
크루스칼 알고리즘 (Kruskal)Programming/알고리즘 2020. 11. 7. 18:11
크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결할 때 쓰이는 알고리즘이다.(ex : 도시를 도로로 연결하고자 할 때 가장 적은 비용으로 연결을 위해 사용) ▷노드 : 출발지와 도착지를 나타내는 지점. ▷간선 : 각 노드를 잇는 선으로 간선마다 비용이 있다. 위와 같이 비용 그래프가 이루어져 있다고 해보자. 크루스칼 알고리즘에서는 총 (노드의 갯수 - 1)개의 간선을 비용이 적은 순서대로 뽑는다. 단, 여기서 중요한 점은 사이클을 형성하지 않는 간선만 선택하는 것이다.(여기에서 앞서 배웠던 Union-Find 알고리즘이 사용된다.) #include #include #include using namespace std; int parent[8]; class Edge { public: int node[..
-
Union-FindProgramming/알고리즘 2020. 11. 7. 17:00
Union-Find는 대표적인 그래프 알고리즘이다. 각 노드들이 서로 같은 그래프에 속해있는지 확인하는 알고리즘으로 서로소 집합(Disjoint-set)이라고도 부른다. 위와 같이 노드가 존재한다고 하자. 초기에 각 노드는 본인의 값을 부모로 가진다. 노드 1 2 3 4 5 6 7 8 9 10 부모 1 2 3 4 5 6 7 8 9 10 Union-Find에서는 보통 부모가 작은 것으로 통일 시켜준다. 만약 위와 같이 1번 2번 노드가 연결되고, 5번과 8번 노드가 연결되면 노드 1 2 3 4 5 6 7 8 9 10 부모 1 1 3 4 5 6 7 5 9 10 위와 같이 테이블이 변경된다! #include using namespace std; int parent[11]; // 부모를 찾는 함수 (재귀 사용)..