알고리즘 워밍업

연산자

연산자는 연산을 의미하는 기호나 문자열입니다. 연산자의 종류는 덧셈,뺄셈,나눗셈,곱셈의 사칙연산을 하는 산술연산자, 값의 크기를 비교하는 비교 연산자, 조건을 연결하거나 부정하는 논리연산자가 있습니다. 프로그래밍 언어의 종류에 따라 특수연산자도 있지만 일반적인 연산자만 알아도 충분합니다.

 

유클리드 호제법

유클리드 호제법은 두 정수의 최대공약수를 구하는 알고리즘입니다. 여기서는 변수 두개에 저장된 정수의 ㅚ대공약수를 구해서 화면에 표시합니다. 다음은 유클리드 호제법의 일반적인 알고리즘을 설명합니다.

1. 두 정수의 큰 쪽에서 작은 쪽을 빼는 것을, 양쪽이 같아질때까지 반복

2. 가아진 값이 최대 공약수가 됩니다.

~가 될때까지 반복한다는 의사코드, c , 자바에서는 ~라면 반보간다로 바꿀 필요가 있습니다. 양쪽이 같아질때까지 반복한다는 조건을 ~라면 반복한다로 바꾸면 양쪽이 동일하지 않으면 반복한다가 됩니다. 주의 해야합니다.

큰쪽에서 작은 쪽을 뺄때 양쪽이 같지 않다면 반복합니다.

유클리드 호제법은 알고리즘이란 무엇인가를 설명하는 소재로 자주 사용됩니다.  알고리즘은 명확하고 유한해야한다. 인간의 직감에 의존해 애매모호한 부분이 있거나 언제 끝날지 모르는 절차는 알고리즘이라 할 수 없다.

예시로 30과 50의 최대공약수를 구하면 우리는 산수로 구할수있지만 이 절차는 애매한 부분이 있습니다. 30을 나눌 수 있는 소수가 2,3,5인것을 어떻게 알지 컴퓨터는 파악해야하는데 이것은 인간의 직감에 알뿐이지 컴퓨터는 할 수 없다. 

그러나 유클리드 호제법은 애매모호한 부분이 없다. 유클리드 호제법을 사용해 1234567과 7654321의 최대공약수를 구할때 직접 손으로 계산하는 일은 하지 않는것이 좋다. 프로그램을 만들어 조사한 결과 뺄셈을 어마어마하게 많이 해야하기에 우리는 하기 힘들지만 컴퓨터는 금방 할 수있는 일이기에 컴퓨터로 작업을 돌려야한다.

 

알고리즘의 추적

그럼 어떻게 유클리드 호제법으로 최대 공약수를 구할 수 있는 지 알아봅시다. 수학적인 증명이 아니라 알고리즘은 자체는 명확히 이해해야하지만, 알고리즘 구조는 그림으로도 충분히 이해할수있다. 알고리즘의 구조는 모르지만 제시된 순서대로 해보니 답을 구할 수 있다는 온전한 정답이 아닙니다. 그림으로 구조를 이해하면 이해가 훨씬 쉬울것입니다. 또한 다른 문제를 풀때 응용도 가능합니다.