알고리즘이란

알고리즘

알고리즘은 입력(input)을 출력(output)으로 변환하기 위한 일련의 계산절차(computational procedure)입니다. 즉, 알고리즘은 잘 정의된 계산문제(computational problem)를 해결하기 위한 도구입니다.

 

잘 정의 된 계산문제(well defined computational problem)

잘 정의된 계산문제란 입력과 출력의 관계를 일반적인 용어를 사용해서 정의한 문제입니다. 특정한 입력값 하나를 의미하는 것이 아니라, 어떤 형태의 입력이 주어졌을 때 어떤 출력이 나와야 하는지를 정의한 것입니다.

 

문제의 인스턴스(instance of problem)

특정한 문제에 대해 주어지는 구체적인 입력들을 문제의 인스턴스(instance of problem)라고 부릅니다. 실제 문제를 다룰 때는 보통 이를 입력값이라고 생각하면 됩니다.

 

맞는 알고리즘(corret algorithm)

어떤 문제에 대한 알고리즘이 입력으로 제공된 모든 인스턴스에 대해 정확한 출력을 제공하고, 계산이 끝나면서 정지한다면 그 알고리즘은 맞는 알고리즘입니다. 문제를 풀고도 정지를 하지 않거나, 정확하지 않은 출력을 제공하면 맞지 않은 알고리즘입니다.

 

성능(Efficiency)

컴퓨터는 하드웨어이기 때문에 자원이 무한하지 않습니다. 따라서 알고리즘을 구성할 때는 시간과 메모리를 함께 고려해야 합니다. 컴퓨터의 성능이 1000배 이상 차이 나더라도, 알고리즘에 따라서는 더 느린 컴퓨터가 더 빠르게 결과를 낼 수 있습니다. 이 때문에 알고리즘은 단순한 구현 방법이 아니라 하나의 기술적 체계라고 볼 수 있습니다.