CS 공부/알고리즘
유클리드 호제법
유클리드 호제법 유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다. 이 알고리즘은 두 수를 나눈 나머지를 이용해 최대공약수를 구하는 방법이다. 먼저, 큰 수를 작은 수로 나눈 나머지를 구하고, 작은 수를 이전에 구한 나머지로 나눈 나머지를 구한다. 이 과정을 나머지가 0이 될 때까지 반복하다 마지막으로 구한 나머지가 최대공약수가 된다. 조금 더 구체적으로 예를 들자면 49와 21가 있다고 생각해보자 49를 21로 나누어 떨어지지 않으니까 49를 21로 나눈 나머지 값은 7이다. 21을 7로 나누면 나누어 떨어진다.(나머지가 0이 될 때까지 반복한다는 것이 이 뜻) 즉 7이 최대공약수가 되는 것 아래 백준 문제를 풀다가 보게 된 수학공식? 알고리즘? 인데 코드로는 아래처럼 볼 수 있다. [백준] ..
