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

기본적인 개념은 javaScript 와 동일하기 때문에 개념은 아래 링크를 참고하면 좋다. [javascript] 최대공약수와 최소공배수 알고리즘 공부하면서 초등학교 수학으로 돌아가는 경우가 종종 발생했다. 그 중에 하나가 바로 최대공약수와 최소공배수였다. 최대 공약수, GCD : Greatest Common Divisor 두 수 A와 B의 공통된 약수 중 ihyeonspoa.tistory.com 최대공약수를 구하는 방법 def getGcd (num1, num2): gcd = 1 #작은 숫자까지만 범위 지정 minValue = num1 if num1 < num2 else num2 #range(start,end,step)의 end 파라미터는 해당 숫자까지 가지 않음. for x in range(2,minV..

초등학교 때 풀었던 분자끼리 덧셈인데 이걸 코드로 하려니 왜이렇게 머리가 안도는지 힘들었다. 심지어 코딩테스트 입문에 있는 문제인데.... 여기서 현타가 좀 왔었다. 문제 첫 번째 분수의 분자 = number1, 분모 denom1 두 번째 분수의 분자 = number2, 분모 denom2 위와 같이 분자와 분모가 있는 분수가 주어졌을 때, 이 두 분수를 더한 값을 분자와 분모를 순서대로 담은 배열을 return 하라. 단, 기약 분수로 표현해야한다. *제한사항 이 분수는 전부 0보다 크고 1000보다 작다. cf. 영어로 분자는 numerator, 분모는 denominator 라고 한다. pseudo code 1. 분수끼리 더하려면 분모를 최소공배수값으로 바꿔줘야 한다. 2. 최소공배수에 곱한 값 만큼 ..

최대공약수(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. 그중에서 가장 큰녀석을 도출한다. +추가적으로 생각해봐야할 것..