📌 Algorithm

9세기 경 아라비아의 천문학자이자 수학자인 알고리즈미(al-Khowarizmi)의 이름에서 유래되었다. 알고리즈미는 십진법에 의해 덧셈, 뺄셈, 곱셈, 나눗셈, 제곱근, 원주율을 구하는 방법을 아랍어로 기록해 놓았는데, 이런 식으로 사칙연산 및 다양한 산술의 해를 구하는 절차를 공식화 해놓은 기록이 후에 알고리즘으로 발전되었다.

• 문제를 해결하는 최선의 선택
• 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제의 풀이 방법
• 프로그래밍에서는 input 값을 통해 output 값을 얻기 위한 계산 과정

🤔 그렇다면 일련의 절차를 정의하고, 공식화만 시킨다면 전부 알고리즘이라고 볼 수 있을까?

• 문제 해법이 알고리즘이라 명시 되려면 일정한 조건들을 반드시 만족해야만 한다!

✨ 알고리즘 일정 조건

• 입력(Input)

  알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 한다. 꼭 입력을 받지 않아도 되는 알고리즘도 있다. (ex. 원주율(pi)의 1조 번째 자리 수를 구하려는 경우 입력은 없지만 출력은 있다.)

• 출력(Output)

  알고리즘은 실행이 되면 적어도 한 가지 이상의 결과를 반드시 출력해야 한다. 만약 알고리즘에 출력이 없다면 이 알고리즘은 끝이 났는지, 끝이 나지 않았는지 확인할 길이 없기 때문이다. 출력은 알고리즘에서 “끝이 났다" 라는 표현이므로 반드시 존재해야 하며, 이는 유한성과도 연관이 있다.

• 유한성(Finiteness)

  알고리즘은 유한한 명령어를 수행한 후, 유한한 시간 내에 종료해야 한다. 이는 알고리즘은 실행된 후에는 반드시 종료되어야 한다는 말과도 같다. 알고리즘이 무한히 실행이 된다면 무한히 기다려야 할 것이며, 그것은 출력의 기약이 없는 알고리즘일 것이다.

• 명확성(Definiteness)

  알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해서는 안 된다.

• 효율성(Efficiency)

  알고리즘은 가능한 한 효율적이어야 한다. 모든 과정은 명백하게 실행 가능해야 하며, 실행 가능성이 떨어지는 알고리즘은 효율적이지 못한 알고리즘이라 볼 수 있다. 알고리즘은 시간 복잡도와 공간 복잡도를 통해 결정이 되므로, 시간 복잡도와 공간 복잡도가 낮을 수록 효율적인 알고리즘이라 볼 수 있다.