알고리즘을 푸는 도중에 최대공약수에 관한 문제가 나와 정리해봤다. 최대공약수 공약수는2개 이상 정수의 공통적인 약수를 말한다. 최대공약수란 공약수 중의 가장 큰 공약수를 말한다. 예를 들어, 2 와 4의 공약수는 1, 2 이다. 따라서, 최대공약수는 2 이다. 따라서 아래와 같이 함수를 사용해서 나타낼 수 있다. int gcd(int a, int b){ int n; while(b!=0){ n=a%b; a=b; b=n; } return a; } 최소공배수 공배수는 2개 이상의 정수의 공통적인 배수를 말한다. 최소공배수란 공배수 중의 가장 작은 공배수를 말한다. 예를 들어 2 와 4의 공배수는 4, 8, 12, ... 이다. 따라서, 최소공배수는 4 이다. 따라서 아래와 같이 함수를 사용해서 나타내보았다. ..

문제 맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하면 경기력 저하가 나타날 수 있으므로 모든 선수에게 같은 개수를 주려고 한다. 퍼거슨 감독은 사과를 싫어한다. 따라서 사과가 남으면 안 된다. 예를 들어, 퍼거슨이 빨간 사과를 4개, 초록 사과를 8개 가지고 있다면, 다음과 같이 세가지 방법으로 나누어 줄 수 있다. 선수 1명에게 빨간 사과 4개와 초록 사과 8개를 줄 수 있다. 선수 2명에게 빨간 사과 2개와 초록 사과 4개를 각각 줄 수 있다. 선수 4명에게 빨간 사과 1개와 초록 사과 2개를 각각 줄 수 있다. 퍼거슨이 사과를 나누어 주는 방법을 구하는..