알고리즘 (Algorithm)

알고리즘 (Algorithm)

알고리즘이란 어떤 작업을 수행하기 위해 입력을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다.

알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다. 설계하려는 알고리즘이 "무엇을" 하는지는 입력과 출력에 의해 명시할 수 있다.

1. 알고리즘의 명확성

알고리즘이 명확하다는 것은 모호하지 않고 이해하기 쉬움을 뜻한다. 특정 프로그래밍 언어로 변환하는 데 어려움을 느끼지 않을 정도가 되어야 한다. 그렇다고 해서, 특정한 프로그래밍 언어의 문법에 맞추라는 것은 아니다. 이것은 오히려 알고리즘의 명확성을 해칠 수 있다. 명확하다는 것과 자세하다는 것을 혼동하지는 말기 바란다.

2. 알고리즘을 왜 분석하는가?

어떤 알고리즘을 설계하고 나면 이 알고리즘이 자원을 얼마나 소모하는지 분석해야 할 때가 많다. 여기서 자원이란 메모리나 통신대역 등이 될 수도 있지만, 대부분의 경우 소요시간만이 관심의 대상이다. 현대의 컴퓨터는 충분한 양의 메모리를 가지고 있고, 통신 기술 역시 매우 발달해서 아주 비효율적이지 않은 이상 큰 관심의 대상이 되지 않는다. 그에 비해, 프로그램의 처리 속도는 언제나 개발자와 서비스 제공자, 그리고 사용자 모두가 관심을 가지는 분야이기에 일반적으로 알고리즘의 시간적 효율성을 중요시 한다.

시간의 분석은 최악의 경우와 평균적인 경우에 대한 분석이 대표적이다. 시간 분석을 하면 알고리즘이 어느 정도의 입력에 대해서 어느 정도의 시간을 필요로 하는지 미리 짐작할 수 있다. 예를 들어, 데이터베이스에 있는 3천만 명의 고객 레코드를 2시간 내에 생년월일순으로 정렬하라는 요구를 받았을 때, 사용하고자 하는 알고리즘의 소요시간이 입력의 크기에 대해 어떤 함수(지수 함수, 로그함수와 같은 수학적 함수)에 비례하는지를 안다면 주어진 시간에 요구하는 작업을 완료할 수 있을지 대략적으로 짐작할 수 있다.

3. 알고리즘의 수행시간

앞서 말했듯이, 알고리즘의 수행시간은 입력 크기에 대해 시간이 어떤 비율로 소요되는지로 표현한다. 무엇이 입력의 크기인지는 대부분 자명하다. 예를 들어 정렬의 경우, 정렬하고자 하는 개체의 수가 입력의 크기가 된다. 도시간의 최단거리를 구하는 경우에는 계산에 관여하는 됫들의 촉 수와 도시간 간선(도로)의 총 수가 입력의 크기가 된다. 계승을 구하는 경우에는 계승치를 구하고자 하는 자연수의 크기가 입력의 크기가 된다.