알고리즘 설계와 분석
개요
알고리즘이란, 특정한 작업을 수행하기 위한 절차이다. 이에 따라 하나의 알고리즘은 컴퓨터의 종류에 관계 없이 동일한 작업을 동일한 절차로 수행한다. 다만 이를 표현하는 문법이 달라질 뿐이다. 이러한 알고리즘이 잘 작동하기 위해서는 일반적이고(general), 잘 정의된(specified) 문제를 해결할 수 있어야 한다. 이때 잘 만들어진 알고리즘 문제는 그것에 대한 입력으로 주어질 수 있는 인스턴스의 완전한 집합과, 그중 하나의 인스턴스를 입력으로 하였을 때의 정답이 명확하게 설명된다.
예를 들어 정렬(sorting) 문제에 대해 생각해보자. 입력으로는 n개의 수 으로 이루어진 수열이 주어지며, 이때 출력은 해당 수열을 재배열하여 이 되도록 하는 것이다. 이때 이러한 작업을 수행하는 알고리즘은 효율적이고(efficient), 정확해야(correct) 한다. 이때 정확함(correctness)에 대한 개념은 많은 알고리즘 문제에서 명확하지 않다. 따라서 알고리즘에서 정확함을 보장하기 위해서는 이를 증명해야 한다. 이에 대한 더 잘 이해하기 위해서는, Robot Tour Optimization 문제 혹은 Selecting the Right Jobs 문제에 대한 문서를 참조하면 좋다.
Demonstrating Incorrectness
어떤 알고리즘이나 규칙이 항상 최적이라고 주장하기 위해서는, 일반적인 사례에 대해 증명해야 한다. 반대로 이를 부정하기 위해서는 작은 반례 하나만 찾으면 되며, 이는 증명하는 것에 비해서 상대적으로 더욱 쉬운 방법이다. 이러한 반례를 찾는 데에는 아래와 같은 팁들이 존재한다.
- 작은 입력부터 전부 시험해본다.
- 극단적인 예제(아주 크거나 아주 작은 값이 섞여 있는 경우)를 시험해 본다.
- 알고리즘의 각 단계를 밟을 때, 동률(ties)이 존재하는 경우를 살펴본다.[1]
Induction and Recursion
해당 문서에서 다루는 문제/알고리즘
문제
각주
- ↑ 예를 들어 “가장 짧은 interval을 고른다” 했을 때, 길이가 같은 interval이 여러 개 있으면 tie-break 방식에 따라 결과가 달라질 수 있고, 그중 일부는 최적해가 아닐 수 있다.
