목록CS/알고리즘 (9)

하루살이 개발자

[알고리즘] 최대공약수(유클리드 호제법) / 최소 공배수

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..
CS/알고리즘 2022. 2. 23. 11:19
[알고리즘] union-find 알고리즘

* 수학에서 서로소 집합 - 공통 원소가 없는 두 집합 * 서로소 집합 자료구조 - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 연산: union + find 1) union - 2개의 원소로 이루어진 집합을 하나의 집합으로 합치기(합집합) 2) find - 특정 원소가 속한 집합이 뭔지 알려주는 연산 - 서로소 집합 자료구조는 union + find 연산으로 구성되어 union-find 자료구조라 불린다. * 서로소 집합 계산 알고리즘 1) 동작 방법 (1) union 연산 확인 - 서로 연결된 두 노드 확인 -> A의 루트노드 A'와 B의 루트노드 B'찾기(find) -> A'를 B'의 부모 노드로 설정하기(A' < B') (2) 모든 union 연산을 처리할 때까지 (..
CS/알고리즘 2022. 2. 20. 11:15
이전 Prev 1 2 3 4 5 Next 다음