최대공약수 알고리즘

두 수의 최대공약수를 구해야 할 때, 방법은 크게 두 가지라고 할 수 있다.
첫 째, 각 수를 소인수 분해해서 공통된 약수들 중 가장 큰 값을 할당한다.
둘 째, 소인수 분해가 필요없이 유클리드 호제법을 이용한다.

유클리드 호제법
A % B === R 일 때,
A,B의 최대 공약수는 B,R의 최대공약수와 같다.
이를 이용해 최대공약수를 구하는 함수를 가장 간단한 형태로 표현하면
function GCD(A, B) {
return (A % B) === 0 ? N : GCD(B, A % B);
}

시간복잡도와 공간복잡도

시간복잡도(Time Complexity)는 간단히 말하면 프로그램을 얼마나 빨리 실행완료 시킬 수 있는 지의 척도이다.
시간복잡도는 보통 빅오 표기법(Big-O notation)을 이용해서 최악의 경우까지 대비한다.
프로그램 내에서 사용하는 주요변수의 범위와 그 변수에 따라 반복문이나 재귀호출 횟수가 달라진다면,
그 변수가 최대 얼마까지 들어올 수 있는 지를 확인해서 최대 실행횟수가 1억미만이 될 수 있도록 코드를 구성해야 한다.
만약 변수의 최대 크기가 1억이상이라면, 시간복잡도를 O(logn) 으로 설정해서 프로그램 내에서 반복문이 n번미만으로 실행될 수 있도록 알고리즘 구상해야 한다.

공간복잡도(Space Complexity)는 프로그램을 실행시키는 데에 얼마나 많은 자원이 필요한 지에 대한 척도이다. 요즘 같이 하드웨어가 발달한 시점에서 공간복잡도는 시간복잡도에 비해 그 중요도가 떨어지는 것 같지만, 큰 프로젝트를 수행함에 따라 티끌모아 태산인 경우도 생길 수 있고 시간복잡도와 연관성이 있어 비효율적인 알고리즘이 될 수도 있다. 또한 가장 중요한 점은 보통 입사 시험으로 보는 코딩 테스트에는 프로그램 실행 용량 제한이 있다는 것이다. 데이터 1000만개( 80 MB )를 상한으로 생각하고 알고리즘 구성하는 것이 좋다.