최소공배수

단순히 최소공배수를 구하는 문제였다. 다만, 두 수가 서로소 일경우는 if(b==1)이 없이는 무한루프가 돌 수 있기 때문에 b==1 이란 블락을 하나 생성하여 추가해줬다. 최소 공배수는 알다싶이, (a*b)%gcd 로 계산할 수 있다. 주의할 점은 문제에서 언급한대로 값이 크기 때문에 long long int를 사용해야 했었다. (...처음에 서로소를 찾는 문제인줄 알고 에라토스 테네스 체를 구현하고 있었는데, 다시 보니까 전혀 아니더라카더라) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include using namespace std; const int MAX = 1000000; int prime[MAX]; int pn; b..

알고리즘이란? 문제를 해결하기 위한 여러 동작들의 모임입니다. 이를 해결하기 위해 수학적이고 논리적으로 정의된 계산 단계에 따라 원하는 출력을 하는 절차를 거칩니다. 통상적으로 알고리즘은 입력과 출력을 갖고 있습니다. 오류가 존재하면 안되는 점(명확성) 그리고 메모리의 가용영역을 고려하여 효율적인 알고리즘을 작서앻야 합니다. 하나의 알고리즘을 예로 들어보겠습니다. 하기 알고리즘은 최대 공약수를 구하는 알고리즘입니다. 최대 공약수라 함은 손으로 쉽게 구할 수 있지만 코드화 하여 알고리즘을 통해 구할 수 있는 부분도 있습니다. 본 알고리즘 로직은 큰 수에서 작은 수를 빼는 가정을 두 수 중 하나가 0이 될 때까지 반복하면, 0이 아닌 수가 최대공약수입니다. 1 2 3 4 5 6 7 algorithm gcd(..