둠선생 연구실

벨만-포드 알고리즘(Bellman-Ford algorithm)은 시작노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 길이(가중치)가 음수인 사이클을 포함하지 않는 모든 그래프를 처리할 수 있다. 또한 길이(가중치)가 음수인 사이클을 포함하는 지도 확인할 수 있다. 시작노드의 거리는 0으로 그리고 나머지 노드까지의 거리는 무한대로 초깃값을 설정하고, 이 값들을 차례로 줄여나가면서 더는 줄일 수 없을때 까지 반복한다. 알고리즘은 n-1번 진행되며, 라운드마다 m개의 간선을 처리하기 때문에 시간복잡도는 O(nm)이다. #include #include #include using namespace std; #define INF 99999999; int main() { // 간선 리스트 (시작노드..

먼저 깊이 우선 탐색은 노드에서 진행할 수 있는 최대 지점까지 진행하고 되돌아오면서 옆으로 넘어가는 방식이다. 아래의 예시에서는 인접리스트로 그래프를 표현했고, 0번 노드에는 1, 3번 노드가 연결되어있다. 1번에는 2, 4번 노드가, 그리고 2번과 4번 노드는 5번과 연결되어있다. #include #include using namespace std; const int N = 6; // 인접리스트 vector adj[N]; //깊이 우선 탐색 bool visited[N]; void dfs(int s) { if (visited[s]) return; visited[s] = true; cout

최소공배수는 a * b 를 a와 b의 최대공약수로 나누면 쉽게 구할 수있다. 최대공약수를 찾기위해 유클리드 호제법을 이용하면 쉽다. 유클리드 호제법이란, a 와 b의 최대공약수를 구하기위해 a%b=c를 사용한다. c가 0이라면 b가 최대공약수이고, c가 0이 아니라면 gcd(a,b) = gcd(b,c)를 계산하면 된다. 15와 6의 최대공약수를 구하자면 15%6 = 3이므로 gcd(15,6) = gcd(6,3)과 같고 gcd(6,3)은 6%3 = 0 이므로 3이 최대공약수가 된다. 이를 코드로 구현하면 아래와 같다. int gcd(int a, int b){ if(b==0) return a; return gcd(b, a%b); } 추가로 확장 유클리드 알고리즘이 존재하는데, 이는 ax + by = c 에서..

소수는 약수가 1과 자기 자신밖에 없는 수이다. 따라서 소수 판정은 2부터 n-1까지의 숫자로 나눠봄으로써 알 수 있다. 하지만 연산량을 조금 줄이기 위해서 한 가지 수학적인 사실을 이용할 수 있다. - 소수는 2부터 $\sqrt{n}$까지의 정수로 나눠보면 알 수있다. 간단하게 증명하자면, 만약 n이 1을 제외한 $\sqrt{n}$ 이하의 정수로 나누어 떨어지지 않는다고 가정하면, $\sqrt{n}$보다 큰 정수 a로 나누어 떨어진다. 하지만 a로 나누어떨어진다면 n/a로도 나누어 떨어진다는 뜻이고, ($a * \frac{n}{a} = n$ 이므로) 하지만 n/a는 $\sqrt{n}$보다 작은 정수이므로 가정에 모순이 발생한다. 따라서 1을 제외한 $\sqrt{n}$이하의 정수로 나누어떨어지지 않는다면..

만약 정렬이 되어있지 않은 1~n까지의 숫자가 들어있는 (중복없이) 크기 n의 배열이 있다고 가정했을 때, 우리가 원하는 임의의 숫자 k의 위치를 찾기 위해선 앞쪽부터 하나씩 탐색해야한다. 만약 최악의 경우는 k가 맨 뒤에 있을 경우인데, 그 경우 우리는 크기의 n의 배열에서 n번 (모두) 확인해야한다. n의 크기가 크지 않거나, 한번만 수행하면 될 경우에는 나쁘지않은 방법일 수도 있다. 하지만 반대로, n의 크기가 매우 크고, k, m, n, l 등 여러 개의 숫자의 위치를 찾아야 한다면, 배열을 정렬한 뒤에 O(logn)의 시간 내에 탐색이 가능하다. 여기에선 배열을 정렬하는 방법 자체에는 집중하지 않는다. 방식은 간단하다 크기 10000인 배열에서 내가 찾고 싶은 수가 100번 째에 있다고 가정하면..

#include #include using namespace std; int main() { map dic; dic["a"] = 1; dic["b"] = 2; dic["c"] = 3; dic["d"] = 4; int a = dic["e"]; map::iterator it; for (it= dic.begin(); it != dic.end(); it++) { cout first

확률에서 이런 경우가 많이 있다. 예를들어, 4명의 후보자가 있다. 그 중에 원하는 사람을 우리 팀에 뽑을 수 있다. 4명을 다 고를 수도 있고, 아무도 안 고를 수 있다면, 우리 팀에 후보자를 데려올 수 있는 경우의 수는 몇 가지인가? 풀이는 간단하다. 각 한명씩 뽑을 경우, 뽑지 않을 경우 두 가지 선택지만 존재하므로, 곱의 법칙을 이용해 2 * 2 * 2 * 2 총 16가지의 경우의 수가 존재한다. 이런식으로 각각의 선택지를 포함하고, 포함하지 않고 모두 탐색해야한다면 어떤식으로 풀어야할까? 아이디어는 간단하다. 0 ~ 15 (선택지가 4개 일 경우) 까지의 숫자를 이진수로 변환하여 각각의 경우에 대응하는 것이다. 모두 다 뽑지 않는 경우는 0 (0000)이 될 것이고, 모두 다 선택하는 경우는 1..

C++의 자료형(타입)을 확인하거나 크기가 궁금할 때는 어떻게 확인할 수 있는 지 알아보자. 결론부터 말하자면, 먼저 자료형은 헤더의 typeid()를 이용한다. 타입의 크기는 sizeof() 함수를 이용하면 구할 수 있다. 아래의 예제 코드를 보자 #include #include using namespace std; int main() { int a = 5; bool b = false; short int c = 15; double d = 25.12; cout