노래부르다

최대공약수 / 최소공배수 문제를 풀때 매우 유용할 것 같아서 블로그에 작성해둔다. 해당 알고리즘 문제만 나온다면 어디서든 쉽게 활용가능하니 꼭 알아두자. 유클리드 호제법 유클리드 호제법이란, 정수 A, B 그리고 이들의 나머지값 R이 있다고 할때,(A % B = R)A, B의 최대공약수가 B, R의 최대공약수와 같다는 원리이다. 이때, A와 B의 대소비교는 중요하지 않음. 10 % 15 = 1015 % 10 = 510 % 5 = 0-> 최대공약수: 5이렇게 쉽게 최대공약수를 산출가능하다. 코드형식은 아래와 같다. int gcd(int a, int b) { int temp; while(b != 0) { temp = a % b; a = b; b = temp; ..

최대공약수를 구하는 유클리드 호제법을 이용한 문제이다. 이에 최대공약수를 구하는 규칙을 모른다면 문제를 못푼다.알고리즘 풀이우리가 아는 유클리드 호제법은 두 수에 대한 최대공약수를 구하는 함수를 알고 있을 것이다.그러나 이번 문제에서는 여러 수의 최대공약수를 구해야하는 문제이다. 그러면 어떻게 할까? -> 생각보다 쉽다. 5개의 수가 있다고 할 때, 1번째 2번째 수의 최대공약수를 N이라 할 때, 3번째 수와 N의 최대공약수를 구하면 된다.어짜피 첫번째, 두번째 수를 0으로 만들 수 있는 최대의 값이 N이기 때문에, N과 3번째수만 비교해도 3개의 수의 최대공약수를 알 수 있다.  해당 방법으로 두 사람이 가진 카드뭉치의 최대공약수 2개를 구한 뒤, 상대방의 카드뭉치를 나눌 수 있는지 없는지 확인하면 된..