자본주의에서 개발자로 살아남기

너비 우선 탐색(BFS, Breadth-First Search) 에 대해서 알아보겠습니다. 목차 1. 너비 우선 탐색( BFS, Breadth-First Search) 의 개념 2. 너비 우선 탐색( BFS, Breadth-First Search) 의 과정 3. 너비 우선 탐색( BFS, Breadth-First Search) 의 구현 1. 너비 우선 탐색( BFS, Breadth-First Search ) 의 개념 너비 우선 탐색은 Breadth First Search 로, 흔히 BFS 로 줄여서 사용합니다. 시작점의 인접한 정점들을 차례로 모두 방문하고, 방문했던 정점을 시작점으로해서 다시 인접한 정점들을 차례로 모두 방문 하는 방식입니다. 즉, 넓게 탐색 하는 것입니다. 너비 우선 탐색(BFS) 는..

최대 공약수 구하기에 대해서 알아보겠습니다. 목차 1. 최대공약수(GCD) 2. 최대공약수(GCD) 구하기 3. 유클리드 호제법 4. Code - C, Java, Python 1. 최대공약수(GCD) 정수의 성질 중 하나로 먼저 공약수란, 두 수 혹은 그 이상의 여러 수의 공통인 약수라는 뜻입니다. 그래서 최대공약수 ( greatest common divisor - GCD ) 는 공약수 중 가장 큰 것이라는 뜻입니다. 두 수 a, b 의 최대공약수를 수학적 기호로 표시하면, gcd(a,b) 이며, 특히 gcd(a,b) = 1 이면 두 수 a,b 는 서로소 라고 합니다. 2. 최대공약수(GCD) 구하기 찾는 법은 간단하다. 약수를 나열하여 공약수를 찾고 그 공약수중에 가장 큰 값을 찾으면 됩니다. 예시로 ..

목차 소수 소수 구하기 에라토스테네스의 체(Sieve of Eratosthenes) 소수 소수 (prime number) 는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 입니다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의됩니다. 예를 들어, 7은 \(1 \times 7 \), \(7 \times 1\) 로 7, 1 만 약수로 가지기 때문에 소수입니다. 그러나 6은 \( 2 \times 3 \) 이라는 자신보다 작은 두 숫자의 곱 으로 나타낼 수 있기 때문에 소수가 아닙니다. 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수 라고 합니다. 소수 구하기 주어진 수가 소수인지 판별하는 문제는 가장 기초적인 문제입니다. 가장 간단한 방법으로는 2부터 n-1 까지의 모든 수..