알고리즘이란?

어떤 문제를 해결하는 절차를 알고리즘(algorithm)이라고 한다.

알고리즘에 관해 자세한 정보를 알고 싶다면 알고리즘 시리즈를 참고해보기 바란다.

프로그램 = 자료구조 + 알고리즘

대부분의 프로그램은 데이터를 처리하고 있고 이들 자료는 자료구조를 사용하여 표현되고 저장된다. 또한 주어진 문제를 처리하는 정차, 즉 알고리즘이 필요하다. 따라서 프로그램은 자료구조와 알고리즘으로 구성되어 있다고 볼 수 있다.

자료구조와 알고리즘은 밀접한 관계가 있어서 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다. 컴퓨터가 복잡한 자료들을 빠르게 저장, 분석, 전송, 갱신하기 위해서는 자료구조가 효율적으로 조작화되어 있어야 한다. 또한 응용 프로그램에 가장 적합한 자료구조와 알고리즘을 선택해야한다.

알고리즘은 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 장치가 이해할 수 있는 언어로 정밀하게 기술한 것이다. 따라서 알고리즘은 특정한 일을 수행하는 명령어들의 집합이다. 여기서 명령어란 컴퓨터에서 수행되는 문장들을 의미한다. 그렇다고 모든 명령어들의 집합이 알고리즘이 되는 것은 아니다.

알고리즘은 다음과 같은 조건들을 만족해야한다.

· 입력 : 0개 이상의 입력이 존재하여야 한다.
· 출력 : 1개 이상의 출력이 존재하여야 한다.
· 명확성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
· 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.
· 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.

알고리즘 기술 방법

알고리즘을 기술하는 방법은 다음과 같이 4가지가 있다.

1. 영어나 한국어와 같은 자연어

이 방법은 자연어를 사용하므로 기술이 편리하지만 모호성을 제거하기 위하여 명령어로 쓰이는 단어들을 명백하게 해야만 알고리즘이 될 수 있다.

ArrayMax(A, n)
1. 배열 A의 첫 번째 요소를 변수 tmp에 복사한다.
2. 요소들을 차례대로 tmp와 비교 후, 더 크면 그 값을 tmp로 복사한다.
3. 배열 A으 모든 요소를 비교 했으면 tmp를 반환한다.

2. 흐름도(flowchart)

흐름도(flowchart)는 명확하게 표현할 수 있다는 잠점이 있어 특허 명세서 등에서 많이 사용된다. 그러나 알고리즘이 조금만 복잡해져도 흐름도가 매우 복잡하게 표시되는 단점이 있다.

3. 유사 코드(pseudo-code)

유사 코드(pseudo-code)는 자연어 보다는 더 쳬계적이지만 프로그래밍 언어보다는 덜 엄격한 언어로서 알고리즘의 표현에 흔히 사용되는 방법이다. 유사 코드의 문법은 보통 실제 프로그래밍 언어와 비슷하여 쉽게 이해가 가능하면서도 특정 프로그래밍 언어로 구현할 때의 여러 가지 문제들을 감출 수 있고, 알고리즘의 핵심적인 내용에 대한 집중할 수 있어 알고리즘의 기술에 많이 사용되고 있다.

ArrayMax(A, n)
tmp <- A[0];
for i<-1 to n-1 do
   if tmp < A[i] then
      tmp <- A[i];
return tmp;

4. 특정한 프로그래밍 언어

이 방법은 특정한 프로그래밍 언어를 사용하여 알고리즘을 기술하는 방법이다. 이것은 알고리즘의 가장 정확한 표현이지만, 구현을 위해 구제적인 사항들을 표함하고 있어 알고리즘의 핵심적인 내용 이해를 방해할 수 있다.

int ArrayMax(int score[], int n)
{
   int tmp = score[0];
   for(int i = 1 ; i < n ; i++)
   {
      if(score[i] > tmp)
      {
         tmp = score[i];
      }
   }
   return tmp;
}