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