알고리즘

알고리즘

알고리즘의 정보과학적 정의는 쉽게 말해서 주어진 문제를 해결하기 위한 단계 또는 절차를 의미한다. 

이 단계나 절차는 입력과 출력 값을 가지고 있어야 하며, 출력을 얻기 위해서 까지 유한한 단계를 가져야 한다는

종료 조건을 가진다. 

일반적으로 프로그래밍 대회들에서는 알고리즘을 평가할 때 문제 풀이가 되는지와 문제풀이를 하는데 사용되는 자원으로 평가하는데

이 자원으로 사용하는 것이 알고리즘의 실행시간이다. 즉, 얼마나 빠른 시간내에 문제를 해결 하느냐이다.

참고로, 임베디드 소프트웨어에서는 이러한 시간을 자원으로 보기보다 한정된 메모리를 자원으로 바라본다. 그 이유는 임베디드 소프트웨어는 하드디스크처럼 보조기억장치를 필수적으로 보유하고 있지 않기 때문에 램의 관리가 중요해 지기 때문이다. 

알고리즘은 크게 3가지 형태로 표현 가능하다. 

먼저 자연어를 통해서 집합 S의 원소들의 합을 구하는 알고리즘을 표현해 보도록 하자. 

알고리즘 A

(1단계) 원소의 인덱스를 id로 정의한다. 

(2단계) 집합 S에 대해여

 

를 구하고 이를 s 라 한다. 

(3단계) s를 출력하고 종료한다. 

 

위의 알고리즘을 의사코드로 표현해 보자

알고리즘 A

위의 두 단계를 거친 알고리즘 A를 C++언어의 프로그램 코드로 완성 시켜보자.

 

void A(int S[], int n){

int s=0;

for(int id =1; id <=n; id++){

s=s+S[id];

printf("%d\n",s);

}

 

위의 제시된 알고리즘의 계산량은 입력크기 n이 증가하면 n의 1차 함수만큼 증가한다는 것을 알 수 있다. 이를 n이라고 표현하며

이를 정보과학에서는

으로 표기한다. 이와 같이 알고리즘의 효율성을 계산량으로 표기하는 방법으로 우리는 점근 식을 사용하고 이들은

 등이 존재한다.