dvpzeekke

'유클리드 호제법'이란? 유클리드 호제법(혹은 유클리드 알고리즘)은 빠르게 최대공약수(GCD)를 구하는 알고리즘입니다. 참고로 GCD는 Greatest Common Divisor의 약어! LCM은 Least Common MultiPle의 약어! '유클리드 호제법'의 원리 두 자연수 a, b가 주어졌을 때, a를 b로 나눈 나머지가 temp라고 하면, temp가 0일 때 b가 최대공약수(GCD)입니다. 만약 temp가 0이 아니면 a에 b값을 넣고, b에 temp값을 넣은 다음 위 과정을 반복합니다. '유클리드 호제법'의 구현 방법 반복문을 이용해 구현하거나 재귀함수를 이용해서 구현할 수 있습니다. 먼저 반복문을 이용해 구현하는 법을 소개하겠습니다. int gcd(int a, int b) { int tem..

다이나믹 프로그래밍과 메모이제이션 알고리즘을 비교해보겠습니다. 다이나믹 프로그래밍은 모든 subproblem들을 전부 구해야하는 문제에 적용하면 좋습니다. 메모이제이션은 모든 subproblem들을 전부 구해야하는 경우, stack에서 왔다갔다하는 overhead가 있기 때문입니다. 반면, 메모이제이션은 subproblem을 전부 다 계산하지 않아도 되는 문제에 적용하면 좋습니다. 이전에 계산한 결과를 다시 계산할 필요가 없기 때문입니다. 코드를 통해 비교 및 이해를 해보도록 하겠습니다. 피보나치 수열을 다이나믹 프로그래밍과 메모이제이션으로 각각 구현해보겠습니다. 먼저 다이나믹 프로그래밍 기법을 이용한 피보나치 수열 구현 방법입니다. int fibonacci(int n) { if (n < 2) { ret..

BFS 알고리즘은 깊이를 우선으로 탐색하는 알고리즘 입니다. 즉, 현재 정점에 갈 수 있는 노드까지 들어가며 탐색합니다. 주로 stack 혹은 재귀함수를 이용해서 구현합니다. c++로 dfs를 구현해보겠습니다. 위 그래프의 1 노드에서 갈 수 있는 노드까지 들어가며 탐색합니다. 아래 코드를 참고해주세요. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include #include using namespace std; vector graph(7, vector ()); vector visit(7, false); void..

BFS 알고리즘은 너비를 우선으로 탐색하는 알고리즘 입니다. 즉, 현재 정점에 연결된 가까운 노드부터 탐구합니다. 주로 queue를 이용해서 구현합니다. c++로 bfs를 구현해보겠습니다. 위 그래프에서 1 노드와 가까운 노드부터 탐색하고 노드 번호를 출력합니다. vector 타입의 graph는 각 노드 간의 연결 정보를 나타냅니다. queue 타입의 q는 노드들이 가까운 순서대로 출력되기 위해 사용됩니다. vector 타입의 visit은 노드 방문 여부를 나타냅니다. 아래 코드를 참고해주세요. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 4..