알고리즘 기초 개념 정리 (역사 / 쉬운 설명 / 예시)

지난 두 블로그 포스팅에서는 인공지능의 역사, 출현, 및 발전과정에 대해서 다뤄보았습니다.

 

인공지능의 역사, 출현, 및 발전과정 요약 1

 

인공지능의 역사, 출현, 및 발전과정 요약 2

 

이번 포스팅에서는 인공지능을 개발하기 위해 가장 기본이 되는 '알고리즘'에 대하여 알아보도록 하겠습니다.

 

알고리즘의 정의

알고리즘이란 문제를 해결하기 위한 명확한 절차나 규칙의 모임입니다.

원래 9세기 바그 다트의 수학자 알-후 워리 지미(Al-Khwarizmi)의 '인도 수 계산법(Algoritmide numero Indorum)'이 12세기 유럽에 전해져 오랫동안 유럽 대학의 교과서가 되었던 것에서 유래되었습니다.

현재는 수학, 컴퓨터 과학, 정보학 분야에서 특히 컴퓨터를 이용한 문제 해법의 학문이 되었습니다.

알고리즘이란 무엇일까요?

알고리즘은 (정보 분야의 교과서에서는 알기 쉬운 예로서) 자주 요리의 레시피에 비유됩니다. 커스터드 크림 레시피를 보면서 거기에서 알고리즘적인 특징을 생각해 봅시다.

 

커스터드 크림 레시피(예시)

- 노른자, 설탕, 밀가루를 불에 지핀다
- 숟가락을 재료에 담그다
- 숟가락을 끄집어내어 숟가락 뒷면을 손가락으로 덧댄다
- 만약 흔적이 뚜렷이 남는다면, 불을 멈추고 식힌다
- 그렇지 않으면 2.부터 반복한다

 

알고리즘적인 특징의 설명

1. 명확한 절차 제공: 레시피는 커스터드 크림을 만들기 위한 상세한 절차를 제공합니다. 알고리즘 또한 문제를 해결하기 위한 명확한 단계를 정의합니다.
2. 입력과 출력: 레시피에서는 입력(재료)과 출력(완성된 커스터드 크림)이 명확하게 정의되어 있습니다. 알고리즘도 특정 입력을 취하여 기대되는 출력을 합니다.
3. 재현성: 레시피를 정확하게 따르면 어떤 사람이든 비슷한 커스터드 크림을 만들 수 있습니다. 마찬가지로 알고리즘은 같은 입력에 대해서는 항상 같은 출력을 얻을 수 있습니다.
4. 조건과 반복 : 레시피 중 '만약 흔적이 선명하게 남는다면'과 같은 조건이 설정되어 반복합니다. 알고리즘에서도 특정 조건을 충족할 때까지 반복합니다.
5. 효율성: 레시피는 시간과 노력을 최소화하기 위한 효율적인 절차입니다. 알고리즘도 가능한 한 적은 계산량으로 목적을 달성하기 위한 절차를 목표로 합니다.

"프로그래밍 언어를 배웠는데 프로그래밍을 잘 모르겠어요"라고 고민하고 있는 학생이 더러 있습니다. 하지만 언어를 배운다는 것은 '다지기' 등 도구 사용법을 습득한 것과 같습니다. 역시 레시피도 배워야 요리를 만들 수 있습니다.

 

가장 오래된 알고리즘: 유클리드의 호제법

유클리드의 호제법(Euclidean algorithm)은 서기 전 300년경 고대 그리스 수학자 유클리드가 "원론"이라는 저작 속에서 소개한 것으로 알려져 있습니다. 이는 2개의 자연수 최대공약수(GCD)를 구하기 위한 알고리즘으로 기록에 남는 가장 오래된 알고리즘 중 하나로 여겨지고 있습니다.

 

유클리드의 호제법의 기본적인 개념은 '2개의 수 a와 b(여기서 a>b)의 최대공약수 GCD(a,b)는 b와 a를 b로 나눈 나머지(r)의 최대공약수와 같다'는 것입니다. 즉,

GCD (a,b) = GCD (b,r)

 

가 됩니다.

 

나머지를 구하는 순서를 r이 0이 될 때까지 반복합니다. 그렇다면 a와 b의 최대공약수는 r이 0이 되었을 때 b의 값일 것입니다.

 

알고리즘의 절차와 구체적인 예

알고리즘은 명확한 절차(즉 누가 실행해도 같은 결과를 얻을 수 있는 절차)로서 표현할 수 있습니다.

1. 자연수 a와 b를 준비합니다. (a>b라고 가정)
2. a를 b로 나눈 나머지 r을 계산합니다.
3. b를 새로운 a라고 하고 r을 새로운 b라고 합니다.
4. b가 0이 될 때까지 순서 2와 순서 3을 반복합니다.
5. b가 0이 되었을 때의 a의 값이 최대공약수가 됩니다.

그리고 이 절차는 구체적인 예를 주어 정말로 결과를 얻을 수 있는지 확인해 봄으로써 이해를 확인할 수 있습니다.

 

예를 들어서, a는 42, b는 12라고 가정해 봅시다.

1. a = 42, b = 12
2. r = 42 mod 12 = 6
3. a = 12, b = 6
(b가 0이 아니기 때문에 순서대로 2로 돌아간다)
2. r = 12 mod 6 = 0
3. a = 6, b = 0
(b가 0이므로 최대공약수는 a=6)

 

프로그래밍에 의한 순서(코드화)

알고리즘의 큰 특징에 재현성이 있습니다. 만약 절차가 옳다면 누가 실행해도 같은 올바른 결과를 얻을 수 있다는 것을 의미합니다. 프로그래밍 언어에 따라 절차를 지시하면(흔히 코드를 짠다고 말하기도 합니다.) 컴퓨터가 알고리즘을 처리하도록 할 수 있습니다.