Tagged: 알고리즘

알고리즘 – 최대공약수(Great Common Divisor)

분수 알고리즘에서 마지막으로 약분(reduce a Fraction to Lowest Terms) 을 합니다. 약분은 분자와 분모의 최대공약수(GCD, Great Common Divisor)로 나누는 것을 말합니다. 따라서 약분을 하기 위해서는 최대공약수를 구하면 됩니다.

약분, 최대공약수를 구하라.

최대공약수 구하기 1

최대공약수를 구하는 방법은 여러가지가 있는데 그 첫번째로 분자, 분모 두개를 동시에 나누었을때에 나머지가 없는 수를 구하면 됩니다. 1부터 시작해서 분자, 분모 두수중에 작은 수까지 대입해서 하나씩 나누어서 0이 되는지를 찾아보는 겁니다.

최대공약수를 구하는 무한대입법이라고 보시면 됩니다.

작은 수가 무엇인지를 구하기 위해서 min 함수를 이용했습니다. 무한대입법을 이용하기 위해서 for 문을 이용했고, maxDiv 변수에 최대공약수 값을 저장하도록 했습니다.

근데, 이렇게하면 아시겠지만 아주 큰수의 경우에 아주 오래 걸립니다. for 문 그냥 막 돌아야하니까요.

최대공약수 구하기 2 – 뺄셈이용.

이 방법을 유클리드(Euclidean) 방법인지는 모르겠습니다. 유클리드 방법은 나눗셈을 이용하는 방법인데, 이것을 뺄셈으로 변환한 것으로 보이거든요.

두 숫자가 있다고 합시다. 두 숫자를 관호에 넣고 왼쪽엔 큰 숫자, 오른쪽엔 작은 숫자를 넣습니다. 그리고 이 둘을 뺀 값을 제수로 넣습니다. 그리고 다시 큰 수를 왼쪽에 넣고 다시 빼고 나온 값을 다시 제수로 넣고 이를 반복하다 보면 나머지가 0일때에 피제수값이 나오는데 이게 바로 최대공약수 입니다.

(3654, 1365)

이 둘을 빼면 2289 값이 나옵니다. 그러면 3654(제수)를 버리고 다음과 같이 적습니다.

(2289, 1365)

다시 둘을 빼면 다음과 같이 나옵니다.

(924, 1365)

왼쪽에는 항상 큰 숫자여야 해서 이 둘을 교환합니다.

(1365, 924)

이것을 한눈에 알아보도록 표기를 하면 다음과 같습니다.

위와 같은 방법이 되고 마지막에 (0, 21) 이니까 두수의 최대공약수는 21 이 되는 것입니다.

이 방법이 유클리드 호제법과 같다는 이유는 뺄셈하는 방법이지만 제수를 항상 나머지로 다시 넣기 때문입니다. 유클리드 호제법은 나눗셈을 이용해서 나온 나머지를 다시 제수로 넣는 방법인데 둘은 같습니다.

(3654, 1365) = (2289, 1365)

이를 공식으로 쓰면,,,

3654 = 1365*1 + 2289

이는 3654/1365 를 나눈 나머지 2289 랑 같습니다.

여기서 규칙은 한가지, 두수를 비교해서 큰수를 왼쪽에 넣어준다 입니다.

최대공약수 구하기 2 – 나눗셈이용.

이를 유클리드 호제법이라고 합니다. 앞에 뺄셈을 나눗셈으로 바꿔서 하는 방법입니다. 이게 뺄셈보다 좋은 점은 반복적인 뺄셈을 없애줍니다. 규측인 뺄셈과 같습니다.

위와같이 while 문을 이용해서 할수도 있지만 재귀호출(Recusive) 로도 다음과 같이 구현할 수 있습니다.

최대공약수(GCD)를 구했는데, 1이 값으로 나온다면 이는 최대공약수가 없다는 것을 의미합니다. 1은 모든수의 공약수이기 때문입니다.

Creative Commons License
알고리즘 – 약분(reduce a Fraction to Lowest Terms) by Voyager of Linux is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

알고리즘 – 분수(Fraction) 문제

알고리즘 – 분수(Fraction) 문제는 컴퓨터 알고리즘을 시작하는데 좋은 예제입니다. 분수는 어릴적 산수시간에 배운 그게 맞습니다. 1/2, 1/3, 1/4 식 입니다.

분수에는도 사칙연산을 할 수 있습니다. 더하기(add), 빼기(subtract), 곱셈(multiply), 나눗셈(divide) 가 그것입니다. 이를 컴퓨터 프로그램 언어를 이용해서 만들어보는 겁니다.

참고: http://interactivepython.org/runestone/static/pythonds/Introduction/ObjectOrientedProgramminginPythonDefiningClasses.html#a-fraction-class

분수의 정의와 제약사항

분수는 다음과 같이 정의됩니다.

수학에서 분수(分數, fraction)는 a/b 이나  \frac {a} {b} 꼴로 표시한다. 이것은 a를 b로 나눈 값, 즉 a와 b의 를 뜻하며, 여기서 a는 분자b는 분모라고 한다. 이 때 분모 b에 0이 들어가는  \frac {a} {0}(a는 상수)라는 수는 정의될 수 없으므로 b0 이어야 한다.

From 위키페디아

중요한 것이 분모는 0 이여서는 안됩니다. 또 한가지 이 글에서 제약조건을 걸어야 하는데, 분자와 분모 모두 양수로만 이루어진 분수를 다룹니다. 또, 모두 정수여야 합니다. 이를 정리하면 다음과 같습니다.

  • 분모는 0 이여서는 안됩니다.
  • 분자, 분모는 모두 양의 정수(양수이며 정수)

분수의 덧셈

분수의 덧셈은 먼저 분모를 ‘통분’해야 합니다. 무슨말이냐 하면 덧셈을 하기 위한 두개의 분수들의 분모 크기를 같은 값으로 만드는 것(=분모를 통일하는것)입니다. 예를들어

1/2 + 1/3 이 있다면 분모를 통분하는데 서로서로 분모값을 분자,분모에 곱해주면 됩니다. (1*3)/(2*3) + (1*2)/(3*2) = 3/6 + 2/6 = 5/6

분모가 같아지니까 분자만 그대로 더해주면 됩니다.

분수의 뺄셈

분수의 뺄셈은 분수의 덧셈과 마찬가지로 분모를 통분해주고 분자까리 빼주면 됩니다.

분수의 곳셈

분자는 분자까리, 분모는 분모끼리 곳해주면 끝~

분수의 나눗셈

나누는 분수을 역으로 바꾸고 둘을 곱셈하면 된다.

2/5 나누기 1/3 = 2/5 * 3/1 = 6/5

여기까지가 분수에 관한 수학적 알고리즘입니다.

컴퓨터 알고리즘

컴퓨터 알고리즘은 컴퓨터를 이용해서 문제를 해결하는 방법입니다. 그럴려면 아무래도 프로그래밍을 해야하고 프로그래밍을 위해서는 프로그램 언어를 이용해야 합니다. Python, Java, PHP 등이 여기에 속합니다.

한가지 컴퓨터 알고리즘을 할때에는 선택한 언어의 특성을 이용하는 경우가 있습니다. 예를들어 Python 을 이용할 경우에 내장 메소드를 이용할 수 있는데, 이번 분수 알고리즘에서 이를 사용할 것입니다. 다른 언어로 구현할 경우에는 이러한 Python 의 내장 메소드 기능을 제공하지 않기 때문에 다르게 구현을 해야합니다.

이 말은 결국 컴퓨터 알고리즘을 구현하는데 사용하는 언어에 영향을 어느정도 받는다는 것입니다.

Python 의 특징(python3.4 기준)

Python 은 내장 메소드를 지원합니다. 이는 모든 데이터를 객체로 인식하고 레퍼런스하기 때문에 가능한 것입니다. 단순한 숫자조차도 다양한 메소드를 지원합니다.

위에 보시면 숫자에 대한 내장 메소드를 볼수 있습니다. 이 내장 메소드들은 특정한 연산을할때에 자동으로 작동합니다. 예를들어, ‘__add__’ 의 경우는 숫자를 더할때에 자동적으로 호출되어 작동합니다.

Python 에서 사칙연산에 관한 내장 메소드는 다음과 같습니다.

구현하기

Fraction 이라는 클래스를 만들고 내장 함수들을 조작함으로써 완성함으로써 완성됩니다.

먼저 두개의 숫자를 입력받는걸로 분수를 만듭니다.

그리고 덧셈 테스트를 해봅니다.

같은 클래스의 객체를 만들어서 덧셈을 해보면 저렇게 내장 메소드가 없다라고 나옵니다. 그러면 저 내장 메소드를 만들어주면 됩니다.

위와같이 덧셈 내장 메소드를 정의해주고 다음과 같이 테스트를 합니다.

잘 되네요. 뺄셈, 곱셈, 나눗셈은 앞에서 말한 방법대로 내장 메소드를 이용해서 구현하면 됩니다.

제약조건인 음수와 0에 대한 것을 예외로 처리하였습니다. 다음과 같이 실행 합니다.

마이너스(-) 표시가 마음에 안들긴하지만 일단 구현까지만하는 걸로..

Creative Commons License
알고리즘 – 분수(Fraction) 문제 by Voyager of Linux is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Stack 알고리즘.

스택(Stack) 알고리즘.

흔희들 스택(Stack) 알고리즘을 가장 단순한 것으로 생각한다. 아니 다시말해서 가장 단순한 것으로 생각한 나머지 별 할일 없는 알고리즘으로까지 치부하는게 문제다. 하지만 스택 알고리즘은 가장 단순하면서 그 단순함으로 인해서 가장 강력하고 널리쓰이는 알고리즘이다.

스택(Stack) 을 말할때에 가장 먼저 떠오르는 것이 LIFO 다. Last-In First-Out. 가장 나중에 들어간 데이터가 가정 먼저 나온다는 것을 영어로 표현한 것인데, 이것을 다른 관점에서 생각해보면 역정렬 알고리즘에 일종이기도 하다.

reverse_order
Figure1. Reverse Order by Stack

스택에 넣었다 꺼내면 역정렬된 상태가 된다.

이를 잘 활용할 수 있는 것이 있는데, 진수 변환이다. 10진수를 2진수로 진수 변환할때를 보자.

Stack 알고리즘
Figure2. Stack 알고리즘

중학교때 배웠던 10진수를 2진수로 만드는 수학 방법이다. 이것을 자세히 보면 나머지로 나오는 것들을 스택에쌓아두고 역으로 뽑아내면 그것이 바로 이진수가 된다는 사실을 알 수 있다.

스택의 또 다른 용법에는 체커(Checker) 도 있다.

위는 간단한 PHP문법이다. PHP는 함수를 사용하거나 조건문과 같은 문법을 사용할때에 ‘{‘ 를 사용한다. ‘{‘ 로 열고 ‘}’로 닫는 식이다. 그래서 항상 쌍으로 존재하는데, PHP 컴파일러는 이러한 것이 오류가 없는지를 어떻게 체크를 할까?

다음과 같이 스택을 이용하면 간단히 체크할 수 있다.

Stack 의 괄호 체크.
Figure3. Stack 의 괄호 체크.

처음에 ‘{‘ 를 만나면 스택에 넣는다. 그리고 ‘}’를 만나면 스택에서 제거한다. 최종적으로 더 이상 빼내야할 ‘{‘ 이 없고 스택이 텅 비어있다면 PHP 컴파일러는 문법으로 쓰이는 ‘{‘ 가 제대로 사용되었다라고 판단한다. 그래서 위 PHP의 예제를 스택을 이용해서 체크해보면 ‘{‘ 가 스택에 하나 남게되어 PHP 문법에 오류가 있다는 것을 알 수 있다.

 

Creative Commons License
Stack 알고리즘. by Voyager of Linux is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.