본문 바로가기

2004

[Algorithm] 정수론 및 조합론(백준 2981,2004번)
Algorithm&Data Structure 2023. 1. 25. [Algorithm] 정수론 및 조합론(백준 2981,2004번) 백준 알고리즘을 풀면서 각 단계를 마칠 때마다 해당 단계에서 배운 점을 정리해 보면 좋을 것 같아서 복습 겸 풀었던 단계들을 먼저 정리해 보려고 한다. 정수론 정수론에서는 최소 공배수, 최대 공약수에 대한 개념이 주로 나왔던 것 같다. 최대 공약수를 유클리드 호제법이라는 알고리즘을 사용해 구하면 시간 복잡도를 O(N)에서 O(logN)으로 줄일 수 있다. 10과 12의 최대 공약수를 구한다고 해보자. 위와 같이 쉽게 구할 수 있다. 코드로 나타내면 아래와 같다. def gcd(a,b): while b: a,b=b,a%b return a 최소 공배수는 최대 공약수를 이용하면 바로 구할 수 있다. 두 수의 곱을 최대 공약수로 나누면 최소 공배수이다. 코드로 나타내면 아래와 같다. def lcm(a,b): r..

티스토리툴바