코딩에서 낭만을 찾으면 안될까요

최대공약수(GCD) 와 최소공배수(LCM)를 구한다면 알아두어야 할 것이 있었다. (문제 풀다보니 자꾸 틀리단다.) 특히나, 알고리즘을 통해서 접근할 때는 효율성에 입각해서 이것을 써야하는 경우가 있다. 시간복잡도를 줄여야 하는 경우가 있다. 그경우 사용할 수 있는 것이 바로 유클리드 호제법이다. 이전에 살펴본 바와 같이 GCD와 LCM은 시간복잡도가 각각 O(N)이다. 이미 O(N)도 훌륭하지만.. 이것을 O(logN)으로 만드는 것이 바로 유클리드 호제법이다. 문송한 관계로 이해하는데 큰 어려움과 궁금증이 있었다. (분명 초중시절 배운걸텐데 1도 기억이 안난다...) 그것을 토대로 문송한 사람이 이해하는 과정에 대해서 포스팅 해본다. 최대공약수와 최소공배수에 대한 개념은 아래 포스팅. [javascr..

알고리즘 공부하면서 초등학교 수학으로 돌아가는 경우가 종종 발생했다. 그 중에 하나가 바로 최대공약수와 최소공배수였다. 최대 공약수, GCD : Greatest Common Divisor 두 수 A와 B의 공통된 약수 중에 가장 큰 정수이다. 4와 2의 최대공약수는 무엇일까? 직관적으로 1초만에 답이 나온다. 2다. 왜냐하면 2는 4를 나눌 수 있는 가장 큰 약수이며, 2는 자기 자신을 약수로 하기 때문이다. 몸(?)은 이미 알고 있다. 하지만 이걸 코드로 구현하자니.. pseudo code에 대해 생각해보기로 했다. 1. 숫자를 2개 받아야 한다. 2. 루프를 돌며 각각의 수를 나누어서 둘다 나머지가 0이 되는 '약수'를 먼저 찾는다. 3. 그중에서 가장 큰녀석을 도출한다. +추가적으로 생각해봐야할 것..