컴퓨터에게 생각을 만들어 주기 : 알고리즘의 유래와 정의

유독 컴퓨터 프로그래밍을 조금씩 접하다보면 알고리즘 이라는 단어를 심심치 않게 접합니다. 그래서 도대체 알고리즘이 뭔데? 알고리즘은 어떠한 문제를 해결하기 위한 여러 동작들의 모임입니다(여러 동작??). 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있고, 수학과 컴퓨터 과학에서의 알고리즘이란 작동이 일어나게 내재하는 단계적 집합입니다. 특히 알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행합니다. 이 단어는 페르시아의 수학자이던 알콰리즈미의 이름에서 따온 것이라고 합니다.(위키피디아 참조)

삼천포로 잠깐 빠져보자면 알콰리즈미는 누구일까요? 일명 아라비아 수학의 위대한 영웅으로 불리는 사람입니다. 알콰리즈미는 십진법을 실생활에서 사용하는 방법에 관해 글을 썻으며, 수학상의 특정한 문제들을 해결하는 방법을 밝혀내고 알렸습니다. 그는 자신의 저서인 "복원과 대비에 관한 책(The Book of Restoring and Balancing)"에서 그런 방법들을 제시했는데, 역시나 목적은 거래, 유산분배, 측량 등을 순쉽게 계산하고자 하는 것에서 시작했다고 합니다. 알콰리즈미가 저술한 복원과 대비에 관한 책은 아랍어로 "키타브 알자브르 왈무카발라"로 불리며, 우리가 알고있는 대수학(algebra)의 영문표기의 어원이기도 합니다.

이처럼 알고리즘은 알콰리즈미가 했던 '문제를 해결하는 쉬운 방법'을 컴퓨터가 능동적으로 처리할 수 있도록 제시하는 것을 말합니다. 따라서 입력, 출력, 명확성, 유한성(종결성), 효율성의 조건을 충족시켜야 알고리즘이라고 할 수 있습니다.

1. 입력 : 외부에서 제공되는 자료가 0개 이상 존재해야 한다.

2. 출력 : 적어도 1개 이상의 서로 다른 결과를 내야 한다.(모든 입력에 하나의 출력이 나오면 안됨)

3. 명확성 : 수행 과정은 명확해야 하고 모호하지 않은 명령어로 구성되어야 한다.

4. 유한성(종결성) : 알고리즘의 명령어들은 끝이 있는 계산을 수행한 후에 종료해야 한다.

5. 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

이런 조건은 알고리즘이 오토마타 이론(Automata Theory)으로 제시된 계산방식을 실체화한 것으로 볼 수 있습니다. 알고리즘과 관련된 연구분야는 고안, 검증, 분석, 테스트로 구분할 수 있습니다.

1. 고안 : 완벽한 자동화를 통한 알고리즘의 개발은 거의 불가능 하지만 이미 증명된 유용한 알고리즘들을 습득하여 유용한 알고리즘을 개발하는 연구

2. 검증 : 고안된 알고리즘이 합당한 입력값에 대하여 올바른 결과를 계산해 내는지를 밝히는 절차가 필요며, 이를 위한 알고리즘 검증은 고안된 알고리즘이 프로그래밍 언어와는 독립적으로 올바르게 작동할 수 있음을 보여주는 데 그 목적이 있음

3. 분석 : 고안된 알고리즘을 실행하기 위해 필요한 실행시간과  필요로 하는 기억장치를 결정하는 것

4. 테스트 : 디버깅, 성능분석

다음으로 알고리즘 설계에 대해서 알아보겠습니다.

유익하셨다면, 공감 꾹! 눌러주세요~!