알고리즘의 개념

- 세상은 알고리즘의 연속이라는 말이 있다. 알고리즘은 주변에서 쉽게 찾을 수 있다. 일반적인 정의는 다음과 같다. "논리정연하게 정의된 규칙들의 집합 또는 유한번의 단계 내에서 문제를 풀기 위한 과정"

컴퓨터에서의 알고리즘의 정의는 다음과 같다.

"컴퓨터를 이용하여 특정 문제를 해결하기 위한 분석 및 체계적인 절차"

컴퓨터 알고리즘이 수행되는 절차는 문제 분석, 문제를 해결하기 위한 알고리즘 설계, 순서도 작성, 검증, 효율성 분석으로 이루어진다.

순서도는 알고리즘을 표준화된 기호와 도형을 이용하여 도식화시킨 것으로 기호는 1962년 국제표준화기구(ISO)에서 정의하였다.

컴퓨터 알고리즘 절차

1. 문제 분석

2. 알고리즘 설계

3. 순서도 작성

4. 정확성 검증

5. 효율성 분석

알고리즘의 특성

알고리즘은 반드시 0개 이상 입력이 있어야 하고 1개 이상의 출력이 있어야 한다. 또한 다음 4가지 특성을 가진다.

• 효율성 - 알고리즘은 주어진 입력에 대해 빠른 시간에 답을 주어야 하며, 메모리 공간도 효율적이어야 한다.
  (시간적, 공간적 효율성)
• 정확성 - 알고리즘은 주어진 입력에 대해 올바른 답을 주어야 한다.
  (결과가 출력되지 않으면 알고리즘으로 분류하지 않는다.)
• 수행성 - 알고리즘의 각 단계는 컴퓨터에서 수행이 되어야 한다.
• 유한성 - 알고리즘은 일정한 시간 내에 반드시 종료되어야 한다.

알고리즘의 유래

알고리즘의 유래는 기원전 300년경에 만들어진 유클리드(Euclid)의 최대공약수를 찾는 알고리즘이다. 최대공약수는 2개이상의 자연수의 공약수들 중에서 가장 큰 수를 말한다.

유클리드(Euclid) 2개 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수가 같다는 성질을 이용하여 최대 공약수를 구했다.

Ex) 24와 14의 최대 공약수는 24-14=10을 계산해서 10과 14의 최대공약수와 동일하다는 성질을 이용하여 다음과 같이 계산하였다. 단, 최대공약수(a, 0)=a 이다.

최대공약수(24, 14)

=최대공약수(24-14, 14) = 최대공약수(10, 14)

=최대공약수(14-10, 10) = 최대공약수(4, 10)

=최대공약수(10-4, 4) = 최대공약수(6, 4)

=최대공약수(6-4, 4) = 최대공약수(2, 4)

=최대공약수(4-2, 2) = 최대공약수(2, 2)

=최대공약수(2-2, 2) = 최대공약수(2, 0)

최대공약수(a, 0)=a 의 조건을 만족 최대공약수 2가 구해진다.

유클리드(Euclid)의 최대공약수 알고리즘에서 뺄셈 대신 나눗셈을 사용하면 더욱 빠르게 최대공약수를 구할 수 있다. 다음은 나눗셈으로 구한 유클리드의 최대공약수 알고리즘이다.

- b가 0이면 큰 수인 a를 최대공약수로 반환

- b가 0이 아니면 a를 b로 나눈 나머지를 결과 만족시까지 재귀호출

다음은 최대공약수(24,14)에 대해 유클리드(Euclid)의 최대공약수 알고리즘이 수행되는 과정이다.

Euclid(24,14)

1번 Line에서 b=14이므로 if (b=0)의 조건이 거짓이된다.

2번 Line에서 Euclid(14,24 mod 14) = Euclid(14, 10)이 된다.

1번 Line에서 b=10이므로 if (b=0)의 조건이 거짓이된다.

2번 Line에서 Euclid(10,14 mod 10) = Euclid(10, 4)이 된다.

1번 Line에서 b=4이므로 if (b=0)의 조건이 거짓이된다.

2번 Line에서 Euclid(4,10 mod 4) = Euclid(4, 2)이 된다.

1번 Line에서 b=2이므로 if (b=0)의 조건이 거짓이된다.

2번 Line에서 Euclid(2,4 mod 2) = Euclid(2, 0)이 된다.

1번 Line에서 b=0이므로 if (b=0)의 조건이 참이 되어 a=2가 최대공약수가 된다.

알고리즘의 표현법

알고리즘을 표현하는 방법은 여러가지 방법이 있겠지만 다음으로 분류하는 것이 일반적이다.

1. 자연어 : 사람이 사용하는 일반적인 언어

2. 순서도 : 알고리즘에 대한 논리적인 절차, 흐름 등을 정해진 약속에 따라 그림으로 표현

3. 의사코드 : 일반적인 언어로 코드를 흉내내 알고리즘을 작성한 코드

4. 프로그래밍 언어 : 컴퓨터에서 사용되는 언어 (Python, C, Java 등)