알고리즘 설계와 분석

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 문제에 대한 문서를 참조하면 좋다.

Demonstrating Incorrectness

어떤 알고리즘이나 규칙이 항상 최적이라고 주장하기 위해서는, 일반적인 사례에 대해 증명해야 한다. 반대로 이를 부정하기 위해서는 작은 반례 하나만 찾으면 되며, 이는 증명하는 것에 비해서 상대적으로 더욱 쉬운 방법이다. 이러한 반례를 찾는 데에는 아래와 같은 팁들이 존재한다.

1. 작은 입력부터 전부 시험해본다.
2. 극단적인 예제(아주 크거나 아주 작은 값이 섞여 있는 경우)를 시험해 본다.
3. 알고리즘의 각 단계를 밟을 때, 동률(ties)이 존재하는 경우를 살펴본다.

Induction and Recursion

반례를 찾지 못했다고 해서 알고리즘이 정확하다는 것은 아니다. 엄밀한 증명이 필요하며, 이를 위해서 많이 사용되는 것이 수학적 귀납법이다. 수학적 귀납법은 재귀적인 알고리즘(recursive algorithm)을 증명하는데 자주 활용된다. 이는 아래와 같은 논리 구조를 따른다.

1. 기저 사례 (basis case): 가장 작은 입력에 대해 올바름을 보임.
2. 귀납 가정 (general assumption): 크기 k 이하에 대해 알고리즘이 맞다고 가정.
3. 귀납 단계 (general case): k+1 크기에 대해서도 올바름을 보임.

알고리즘 분석

알고리즘의 효율성을 분석하는 것은 매우 중요하다. 이를 위해서 사용하는 도구는 (1) 계산의 RAM 모델(the RAM model of computation)과 (2) 계산 복잡도의 점근적 분석이다. 이때 알고리즘 성능을 평가하기 위해서는 “빅 오(Big Oh)” 표기를 사용한다.

The RAM Model of Computation

자세한 내용은 The RAM Model of Computation 문서를 참조하십시오.

The Big Oh Notation

자세한 내용은 The Big Oh Notation 문서를 참조하십시오.

Data Structures

어떤 알고리즘에 알맞은 자료 구조를 이식하는 것은 매우 중요한 일이다. 자료 구조 자체는 프로그램의 정당성(correctness)에 영향을 주지는 않지만, 프로그램의 속도에 매우 큰 영향을 준다. 따라서 자료 구조를 이해하는 것은 알고리즘의 설계와 분석을 위해서는 매우 중요하다.

자세한 내용은 Data Structures 문서를 참조하십시오.

Graph

그래프(Graph)는 알고리즘, 네트워크, 데이터 구조 등 컴퓨터 과학의 여러 분야에서 핵심적인 개념이다.

자세한 내용은 Graph 문서를 참조하십시오.

문제/알고리즘

• Robot Tour Optimization
• Selecting the Right Jobs
• Sorting Problem
• Graph Traversal
• Topological Sorting
• Shortest Paths
• Backtracking
• Dynamic Programming
• Fibonacci Numbers
• Binomial Coefficients
• The Gas Station Problem