알고리즘 설계와 분석

Category:알고리즘 설계와 분석

개요

알고리즘이란, 특정한 작업을 수행하기 위한 절차이다. 이에 따라 하나의 알고리즘은 컴퓨터의 종류에 관계 없이 동일한 작업을 동일한 절차로 수행한다. 다만 이를 표현하는 문법이 달라질 뿐이다. 이러한 알고리즘이 잘 작동하기 위해서는 일반적이고(general), 잘 정의된(specified) 문제를 해결할 수 있어야 한다. 이때 잘 만들어진 알고리즘 문제는 그것에 대한 입력으로 주어질 수 있는 인스턴스의 완전한 집합과, 그중 하나의 인스턴스를 입력으로 하였을 때의 정답이 명확하게 설명된다.

예를 들어 정렬(sorting) 문제에 대해 생각해보자. 입력으로는 n개의 수 $a_1,...,a_n$으로 이루어진 수열이 주어지며, 이때 출력은 해당 수열을 재배열하여 $a{\text{'}}_1\le a{\text{'}}_2\le ...\le a{\text{'}}_n$이 되도록 하는 것이다. 이때 이러한 작업을 수행하는 알고리즘은 효율적이고(efficient), 정확해야(correct) 한다. 이때 정확함(correctness)에 대한 개념은 많은 알고리즘 문제에서 명확하지 않다. 따라서 알고리즘에서 정확함을 보장하기 위해서는 이를 증명해야 한다. 이에 대한 더 잘 이해하기 위해서는, Robot Tour Optimization 문제 혹은 Selecting the Right Jobs 문제에 대한 문서를 참조하면 좋다.

해당 문서에서 다루는 문제/알고리즘

문제

Robot Tour Optimization Selecting the Right Jobs