아카이브/알고리즘

[컴퓨터 알고리즘의 정의] 컴퓨터 알고리즘의 정의와 표현

될성부른떡잎 2015. 7. 4. 16:34


[컴퓨터 알고리즘의 정의] 컴퓨터 알고리즘의 정의와 표현


컴퓨터 알고리즘이란?

컴퓨터를 이용하여 문제를 풀기위한 방법을 과정이나 절차를 이용해 만들어 놓은 것.

컴퓨터가 이해할 수 있는 언어(C, Java...)를 이용해 실행할 내용을 컴퓨터가 할 수 있는 가장 작은 기본 작업의 형태로 만들고 순차적으로 나열한다. 컴퓨터는 지시 사항을 차례대로 하나씩 수행하면서 최종 결과를 얻게 되고 그 결과는 해결하고자 했던 문제의 해답이 된다.


컴퓨터 알고리즘의 정의와 표현

컴퓨터 알고리즘을 정의하고 표현하기 위해서는 크게 4가지 단계를 거친다.


- 문제 정의 (Problem Definition) : 해결하고자 하는 문제. 입력과 출력의 형태로 정의될 수 있어야 하고 컴퓨터가 수행할 수 있는 형태로 전환이 가능해야한다.

- 알고리즘 설명 (Algorithm Description) : 문제를 풀기 위해 수행해야하는 작업을 순서대로 나열하는 것. 일상 언어나 수도 코드등으로 표현.

- 정확성 증명 (Correctness Proof) : 주어진 알고리즘을 수행했을 때 문제를 풀 수 있는지 증명하는 과정. 문제의 해답을 찾아야 하고 정상적으로 종료되는지 확인해야 한다.

- 성능 분석 (Performance Analysis) : 알고리즘이 어떤 문제를 풀기 위해서 필요한 시간이나 공간 혹은 자원들이 얼마나 되는지 비교한다. 모든 알고리즘이 동일한 성능을 가진 컴퓨터에서 절대적인 수행시간을 측정하는건 힘들기 때문에 이를 객관적으로 비교하기 위해 점근적 분석이나 점근적 표기법을 사용한다.