하루살이 개발자

1. 신장 트리 - 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. * 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리의 조건이기도 한다. 2. 최소 신장 트리 - 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 - 크루스칼/프림 알고리즘 1) 크루스칼 알고리즘 - 대표적인 최소 신장 트리 알고리즘이다. - 그리디 알고리즘으로 분류된다. [동작 과정] 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.(비용이 적은 순으로 나열) 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. 2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. ..

1. 최대공약수 구하기 - 두 개의 자연수에 대한 최대공약수를 구하는 유클리드 호제법 알고리즘 이용한다. - 유클리드 호제법 ->두 자연수 a, b에 대하여(a > b) a를 b로 나눈 나머지를 R이라 하면, a와 b의 최대공약수는 b와 R의 최대공약수와 같다. - 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성 def gcd(a, b): if a % b == 0: return b else: return gcd(b, a % b) print(gcd(192, 162)) 2. 최소공배수 구하기 - 서로 다른 수 a, b의 배수중에서 공통되는 배수 중에 가장 작은 값을 의미한다. - 최소공배수는 a, b의 곱을 a, b의 최대 공약수로 나누면 된다. def lcm(a, b): return a * b / g..