전체 글 (132) 썸네일형 리스트형 Lesson 13. Fibonacci numbers - FibFrog #3 (속도 개선) 1. 속도 개선 아이디어아무래도 재귀함수로는 한계가 있어보인다.너비 우선 탐색(BFS, Breadth First Search)을 이용해서 전체 탐색하도록 수정해 보자. 2. 코드 (C++)BFS로 전체 탐색 구현#include int solution(vector &A) { int destination = A.size() + 1; //generate fibonacci numbers vector fib = {}; fib.emplace_back(0); fib.emplace_back(1); int M = 2; int n = fib[1] + fib[0]; while(n leaves = {}; leaves.emplace_back(0); for(size_t i .. Lesson 13. Fibonacci numbers - FibFrog #2 (속도 개선) 1. 속도 개선 아이디어예외처리를 추가해서 재귀 호출을 줄여볼 수 있다.만약 현재까지 점프수가 최소 점프수와 같다면? 더이상 진행할 필요가 없다. 2. 코드 (C++)//Count the minimum number of jumps to the other side of a rivervoid Calculate(int cur_pos, int cur_jump, int& min_jump, vector& fib, vector& leaves){ //added a base case if(cur_jump >= min_jump) return; //arrived at the destination if(leaves[cur_pos] == leaves.back()) { if(cur_jum.. Lesson 13. Fibonacci numbers - FibFrog #1 1. 문제The Fibonacci sequence is defined using the following recursive formula:F(0) = 0 F(1) = 1 F(M) = F(M - 1) + F(M - 2) if M >= 2A small frog wants to get to the other side of a river. The frog is initially located at one bank of the river (position −1) and wants to get to the other bank (position N). The frog can jump over any distance F(K), where F(K) is the K-th Fibonacci number. Luckily, t.. 너비 우선 탐색 (BFS, Breadth First Search) 전체 탐색 방법 중 하나이다.너비 우선 탐색을 구현하기 위해서는 큐(Queue)를 사용해야 한다. Queue선입선출(FIFO, First In First Out) 자료구조.먼저 들어온 데이터가 먼저 나간다. 너비 우선 탐색시작 위치에서부터 차례로 인접한 노드를 탐색하는 방법이다. (이하 생략)이러한 탐색을 계속 반복하여, 모든 노드를 가까운 순서대로 탐색하는 방법이, 너비 우선 탐색이다. Lesson 12. Euclidean algorithm - CommonPrimeDivisors #4 (개선-3) 1. 속도 개선 아이디어두 수(N, M)의 밑이 같다면, 두 수의 소인수는 최대공약수의 밑으로만 구성이 되어있다. (10, 30)의 최대공약수(GCD)를 구해보자.\( 10 = 2 \times 5 \)\( 30 = 2 \times 3 \times 5 \)\( GCD = 2 \times 5 \) 최대공약수를 이용해서 두 수의 소인수를 제거 했을 때, 제거되지 않는 소인수가 있다면?이건 그 수만 가지고 있는 소인수가 된다.즉, 두 수의 소인수는 같지 않다라는 결론에 도달할 수 있다. 이 방법은 소인수의 밑을 찾을 때, 최대공약수를 활용하므로, 이전 코드에서의 불필요한 연산을 줄일 수 있다.이전코드에서는 10과 1000이 같은 소인수들을 가지고 있는지 확인하려면, 10과 1000의 모든 소인수들을 구하고 비교.. Lesson 12. Euclidean algorithm - CommonPrimeDivisors #3 (개선-2) 1. 속도 개선 아이디어최대공약수를 이용하면 예외처리를 추가할 수 있다.(최대공약수 = 1 = 서로소) 2. 코드 (C++)#include #include //최대공약수 구하기int GetCGD(int a, int b){ if(a % b == 0) return b; else return GetCGD(b, a % b);}//소인수 구하기map GetPrimeDivisors(int n){ map prime_divisors = {}; //map int i = 2; while(i (i, 1)); } else { it->second += 1; } // n을 i로 .. Lesson 12. Euclidean algorithm - CommonPrimeDivisors #2 (개선-1) 1. 이전 코드의 문제점에라토스테네스의 체가 너무 커서, 메모리 할당에 실패했다. 2. 개선 아이디어에라토스테네스의 체를 쓰지 않고, 2부터 N까지 하나씩 나눠가며 소인수를 찾는다. 3. 코드 (C++)#include #include //소인수 구하기map GetPrimeDivisors(int n){ map prime_divisors = {}; //map int i = 2; while(i (i, 1)); } else { it->second += 1; } // n을 i로 나누어서, n 값을 줄인다 // 소인수 i가 여러번 쓰일수도 있기 때문에, i.. Lesson 12. Euclidean algorithm - CommonPrimeDivisors #1 1. 문제A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.A prime D is called a prime divisor of a positive integer P if there exists a positive integer K such that D * K = P. For example, 2 and 5 are prime divisors of 20.You are given two positive integers N and M. The goal is to check whether the sets of prime d.. 이전 1 2 3 4 5 6 7 ··· 17 다음
