알고리즘이란?
위키피디아에서 긁어온 알고리즘의 정의는 아래와 같다.
a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation
어떤 클래스에 속하는 문제를 풀기 위해 엄밀하게 정의된 유한절차의 명령어들의 나열.
이걸 쪼개서 이해해보자.
1. 어떤 클래스의 문제를 풀기 위해 :
우리가 풀고자 하는 어떤 문제들의 클래스가 있다. 여기까지는 이해 하기 쉽다. 이 문제들은 어떻게 보면 알고리즘에 외부적으로 존재하는, 알고리즘의 관심 대상이라고 볼 수 있다.
복잡도에 따라 위와 같은 클래스들의 문제들로 나뉜다고 한다.. 무지 어려워 보인다.. 계산이론에서 나오는 내용 같은데, 천천히 공부해보면 좋을 것 같다.
2. 엄밀하게 정의된 :
여기서 조금 아리송 해진다. 엄밀하게 정의된? 왜 엄밀하게 정의 해야 할까? 각 명령어들이 의미론적으로 모호하다면, 즉 다의적이 해석이 가능해서 여러 동작이 가능하다면 그 시점부터 non-deterministic하게 동작하는 랜덤 기계가 만들어 진다.
우리는 컴퓨팅을 하기 위해 컴퓨터를 고안해 냈고, a를 하라고 했는데 b를 하는 그런 기계로는 알고리즘을 작성할 수 없다.
3. 유한절차의 명령어들의 나열 :
마지막으로 이런 명령어들의 나열이 유한하다는 건 어떤 뜻일까? 유한 시간 내에 해답을 내줘야 한다는 의미이다. 어떤 문제를 푸는데 무한 시간이 걸린다면, 그건 알고리즘이 사실상 문제를 풀지 못한다는 뜻과 같다고 봐도 될 것이다.
알고리즘의 설계
알고리즘의 설계는 위에서 정의한 알고리즘의 구조를 잡는 것을 뜻한다. 하나의 문제를 풀기 위해 여러 알고리즘이 고안 될 수 있다.
위의 정의 대로라면, 알고리즘은 미리 잘 정의 된 명령어들의 나열(sequence)인 건데, 한 문제에 해답이 되는 명령어 수열이 유일할 필요는 없다.
다만, 하나의 문제를 푸는 여러 알고리즘 중에서 최소 길이의 명령어 수열은 존재할 것이고, 이 최소 길이의 수열이 최적화 된 알고리즘이 아닐까?
그런 알고리즘을 찾아 내는 것(존재성이 보장 된다면)이 알고리즘 설계의 본질이라고 생각한다. 그리고 그 알고리즘 수열의 최소길이를 러프하게 측정하는 방법이 시간복잡도 라고 할 수 있다.
[1] https://namu.wiki/w/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
