안녕하세요. 오늘은 최대공약수를 구하는 알고리즘을 소개하려고 합니다.사실 키보드 몇 번 치고 금방 찾을 수 있는 간단한 알고리즘이지만, 한 번 생각을 정리하고자 작성합니다.최대공약수를 구하는 알고리즘 중 가장 잘 알려진, 유클리드 호제법을 소개합니다.먼저 최대공약수의 정의부터 짚고 넘어가겠습니다.1. 최대공약수 (Greatest Common Divisor; GCD)$$\text{두 정수의 공약수 중에서 가장 큰 공약수}$$사실 이 정의만으로는 최대공약수를 정의하는데 부족함이 있을 순 있지만, 이해하는 데에는 어려움이 없기에 자세한 정의의 언급은 생략합니다. 2. 유클리드 호제법 (Euclidean algorithm)$$a,b\in ℤ \text{이고, }a\text{를 }b\text{로 나눈 나머지를 }..
전체 글
#include int dp[105];int dis[105],t[105];int where[105],ans[105];int main(){ int M,n,sum=0,i,tmp,j,cnt=0; scanf("%d",&M); scanf("%d",&n); for(i=1;i=0;j--) { if(dis[i]-dis[j]dp[j]+t[i]) { dp[i]=dp[j]+t[i]; where[i]=j; } } else break; } } i=where[n+1]..