벨만 포드 알고리즘(Bellman-Ford algorithm)은 다익스트라 알고리즘과 마찬가지로 하나의 정점에 대한 모든 정점의 최단 거리를 찾는 문제에 적용됩니다. 다익스트라는 음수간선이 존재하면 사용할 수 없지만 벨만 포드 알고리즘은 음수간선이 존재해도 사용할 수 있습니다. 가중치의 합이 0보다 작은 싸이클을 음수 싸이클이라고 하는데, 그래프에 음수 싸이클이 존재하면 벨만 포드 알고리즘을 사용할 수 없습니다. 다음은 벨만 포드 알고리즘이 적용되는 문제입니다. https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의..

다익스트라 알고리즘(Dijkstra Algorithm)은 저명한 컴퓨터 과학자인 에르허츠 다익스트라(Edsger Wybe Dijkstra)가 고안한 간선(Edge)에 가중치가 주어진 그래프에서 정점(Vertex)간의 최단 경로를 찾는 알고리즘입니다. 최단 경로 알고리즘에는 여러 종류가 있지만, 그중에서도 다익스트라 알고리즘은 하나의 정점에 대한 모든 정점의 최단 경로를 찾는데 사용됩니다. 단, 가중치가 음수인 간선이 있으면 사용할 수 없습니다. 처음에 에르허츠 다익스트라가 고안한 다익스트라 알고리즘의 시간복잡도는 정점의 갯수를 $V$, 간선의 갯수를 $E$라고 했을 때, $O(V^2)$였으나, 우선순위 큐(Priority Queue)등을 접목해 그 비용이 $O(E+V log V)$까지 개선되었습니다. 다..

https://www.acmicpc.net/problem/1260 불러오는 중입니다... #include #include #include using namespace std; int graph[1001][1001]; bool visited[1001]; int n, m, v; void dfs(int start) { memset(visited, false, sizeof(visited)); stack s; s.push(start); while (!s.empty()) { int current_node = s.top(); s.pop(); if (!visited[current_node]) { visited[current_node] = true; cout > v; for (int i = 0; i < m; i++) {..

이 포스트는 작성중입니다! int binary_search(int data[], int num, int size) { int left = 0; int right = size - 1; int mid; mid = (left + right) / 2; while (left num) right = mid - 1; else left = mid + 1; mid = (left + right) / 2; } return -1; } 오름차순으로 sort된 size만큼의 크기를 가지고있는 정수 배열 num이 data[]에서 몇번째에 위치하는지를 return 하는 함수입니다. num이 data[]에 존재하지 않는다면 -1을 return 합니다.

학교에서 배운 최대공약수와 최소공배수의 정의는 다음과 같습니다. 최대공약수(GCD, Greatest common divisor): 여러개의 정수중 그들 모두의 약수가 되는 공약수(Common divisor)중 최대값 최소공배수(LCM, Least common multiple): 여러 개의 정수중 그들 모두의 배수가 되는 공배수(Common multiple)중 최소값 우선, 최대공약수는 유클리드 호제법(Euclidean algorithm)을 사용하여 구할 수 있습니다. 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다. 유클리드 호제법의 정확한 설명은 다음과 같습니다. A를 B로 나눈 나머지 값을 R이라고 할 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다 예를 들어서 62와 2..

주: 이 포스트는 작성중입니다. 소수(Prime number)란 1과 자기 자신으로밖에 나누어지지 않는 1을 제외한 정수입니다. 다음은 C++로 구현한 가장 일반적인 소수구하기 알고리즘입니다. #include using namespace std; bool IsPrimeNumber(int n) { if (n