알고리즘 1장 - 알고리즘 개요 -

알고리즘 1장

- 알고리즘 개요 -

 

컴퓨터를 공부할 때 필수적으로 공부하는 분야 중 하나가 바로 알고리즘이다. 또한 다양한 곳에서 알고리즘을 활용한 문제나 대회들이 존재한다. 알고리즘은 크게 문제와 해결 방법으로 구성되어 있다고 할 수 있다. 문제는 알고리즘이 나와야하는 이유이고 해결 방법은 알고리즘의 부분이라고 할 수 있다. 이 때 효율성을 고려하게 되는데 알고리즘이 문제의 해결 방법으로 적절한지에 대한 판단이 필요하다. 또한 알고리즘은 단계적으로 이루어진다. 한 단계씩 넘어가면서 문제 해결에 도달하게 된다.

컴퓨터 알고리즘은 컴퓨터를 이용하여 주어진 문제를 풀기 위한 방법이나 절차이다. 앞에서 말한 문제, 해결 방법, 효율성, 단계적 이라는 단어들을 모두 포함하고 있는 어휘이다. 컴퓨터를 이용해서 어떤 작업을 수행하려면 컴퓨터에게 할 일을 정확하게 하나씩 차례대로 알려줘야 한다. 적당한 느낌을 컴퓨터는 받을 수 없기 때문에 정확한 값을 넣어 주어야한다.

컴퓨터 알고리즘을 설명하기 위해서 4개의 단계가 존재한다. 문제 정의, 알고리즘 설명, 정확성 증명, 성능 분석이 그에 해당한다. 문제 정의는 해결하고자 하는 문제는 무엇인가? 입력과 출력의 형태로 정의할 수 있는가? 등등에 대해 논의하는 부분이다. 알고리즘 설명은 컴퓨터가 수행해야 할 내용을 하나씩 차례대로 정의하는 과정이다. 레시피의 순서와 같게 설명을 한다고 볼 수 있다. 정확성 증명은 알고리즘을 과정대로 수행하게 되면 출력으로 항상 올바른 답을 내보는지를 중점으로 생각한다. 이에 대해 오류가 발생하는지 정상적으로 종료를 하는지를 판단하게 된다. 성능 분석은 수행시간과 사용공간을 따지는 것을 말한다. 하나의 문제에 대해 다양한 알고리즘이 존재할 수 있는데 여기서 더 적절한 알고리즘을 선택하기 위해서는 성능 분석을 수행해야한다.

컴퓨터 알고리즘의 수행시간을 분석할 때 특정 기계에서 수행시간을 측정하는 것은 공정하지 않다. 조건이 동일한 특정 기계에서 모든 알고리즘의 수행시간을 측정해야 하는데 이 방법은 현실적으로 불가능하다. 따라서 수행연산의 횟수를 비교하는 방식으로 성능을 분석해야한다. 특정 비교 대상을 두어 비교 대상이 수행하는 시간에 대해 알고리즘이 얼마나 수행연산을 하는지에 대한 횟수로 분석을 하게 된다. 연산 수행시간은 입력으로 크기가 커지면 커질수록 시간이 많이 걸린다. 따라서 수행시간은 입력 크기 n에 대한 함수로 표시를 하게 된다.

이 때 사용하는 표기법이 점근적 표기법인데 O-notation(빅오 표기), 오메가 표기, 쎄타 표기가 있다. 빅오 표기는 점근적 상한에 대한 값을 나타내게 된다. 특정 함수에 대해 그 함수의 값보다 같거나 높은 쪽에 있는 값을 넣어주어 표기하게 된다. 오메가 표기는 빅오 표기와 반대로 점근적 하한이라고 한다. 쎄타 표기는 빅오 표기와 오메가 표기를 같이 사용한 경우라고 볼 수 있다.