알고리즘 (algorithm)

---

어떠한 문제를 해결하기 위해 정해진 일련의 절차(procedure).

알고리즘의 조건

• 유한한 시간내에
• 항상 정확한 정답을 출력할 것 (주어진 입력값 범위 내에서)

well defined problem

알고리즘은 일반적이고 잘 정의된 문제를 풀어야 한다.

ex)
문제 : 정렬
입력 : n개 키들의 sequence (a_1, a_2, ..., a_n)
출력 : a_1' <= a_2' <= ... <= a'_n-1 <= a'_n을 만족하는 입력 열의 순열(permutation)혹은 재순서화(reordering)

좋은 알고리즘의 특징

정확하고, 효율적이며, 구현하기 쉬운 알고리즘

알고리즘 평가(복잡성)

시간 복잡도: 특정 크기 입력에 대한 알고리즘의 수행시간 분석

공간 복잡도: 특정 크기 입력에 대한 알고리즘의 메모리 사용량 분석

Big-O 표기법(점근 표기법 중 한 기법)

위 이미지는 수학적 정의이다.

<참고>
빅-오메가 표기법: 함수의 하한을 나타내는 표기법
빅-세타 표기법 : 시간복잡도가 정확히 계산 가능할때 표기법

알고리즘의 증명

타당한 수학적 증명은 몇 개의 부분으로 구성된다.

1. 증명하고자 하는 것에 대한 분명하고 정확한 진술(statement)

2. 참이라고 인정되는 가정(assumptions)들이 있어서, 증명의 일부로 사용 가능

3. 가정에서 출발해서 증명하고자 하는 진술에 도달하기까지 일련의 추론(resoning)

4. 증명이 끝났음을 나타내는 ∎이나 Q.E.D.(라틴어구로 따라서 논증이 끝났다.)

사실 증명은 이 알고리즘이 자명하지 않은 정확성 성질을 만족하는 지에 대한 논증이다.
즉 거짓되지 않았을 때만 유용하며, 정확하고 틀리지 않았다는 것을 보여주려는 노력이 필요하다.

논증(argument): 독자들을 설득시키기 위한 목적으로 정당한 근거나 일반적인 원리를 들어 주장을 펼치는 것

알고리즘 표현

알고리즘에 관한 추론은 다음 형태를 주의 깊게 기술해야 가능하다.

1. 자연어
2. 의사코드(pseudocode)
3. 프로그래밍 언어

세 가지 표현 방법은 트레이드 오프로 장단점이 존재한다.
자연어는 표현은 쉽지만, 가장 정밀하지 못하다.
프로그래밍 언어는 가장 정밀하지만, 이해가 어렵다.
중간에 해당하는 의사코드가 보통 유용할 때가 많다. (의사코드는 쉽게 말하자면 문법 에러가 절대 발생하지 않는 언어이다.)

내가 원하는 대로 익숙한 방법을 쓰면 된다. 아이디어는 자연어로, 세부 사항을 다룰때는 의사코드와 프로그래밍 언어를 사용하는 방식으로 써도 된다.

알고리즘의 핵심은 아이디어이고 이걸 표현할때 아이디어가 분명하게 드러나지 않으면, 너무 낮은 수준의 표기법을 사용하는 것이다.

문제와 성질

알고리즘 정확성 증명은 알고리즘 기술만으로 이루어지지 않는다. 풀려고 하는 문제도 주의 깊게 기술해야한다.

문제를 기술할 때 다음 두 부분이 명기되어야 한다.
1. 허용되는 입력 사례들의 집합
2. 알고리즘의 출력이 가져야 하는 성질
모호하게 기술된 문제에 대한 알고리즘의 정확성을 증명하는 것은 불가능하다. 잘못된 문제는 잘못된 답을 만든다.

정확하고 효율적인 알고리즘이 존재할 때까지 허용하는 입력 사례의 집합을 좁혀 나가는 것으 알고리즘을 설계할때 중요하고 훌륭한 기법이다.
ex) 그래프 대신 트리, 2차원 대신 1차원

문제의 출력도 함정이 있다.
1. 잘 정의되지 않은 질문을 하는 것이다.
ex) 최선의 경로를 구하라에서 최선이 뭔지 정의해주지 않는 것.

2. 복합적인 목표를 설정하는 것.
   ex) a에서 b까지 회전의 횟수가 꼭 필요한 것의 2배를 넘지 않는 최단 경로를 찾아라
   이건 잘 정의되어 있지만 추론하고 풀기에 너무 복잡하다.

부정확성 증명

가장 좋은 방법은 반례를 만드는 것이다. 좋은 반례는 두 가지 특성을 가진다.

1. 검증 가능성(Verifiability) : 특정 사례가 알고리즘의 반례가 된다고 주장하기 위해서는 a. 이 사례에 대한 알고리즘의 해를 계산 해야하고, b. 더 좋은 해를 제시함으로써 알고리즘이 그것을 찾지 못했음을 보여야한다.

2. 단순성(simplicity) : 좋은 반례는 불필요한 세부 사항을 제거해야 한다. 그래야 왜 알고리즘이 실패하는지 그 이유가 분명해진다. 일단 반례를 발견하면, 핵심만 남기고 단순화할 가치가 있다.

반례는 어떻게 찾으면 좋을까? 몇 가지 기술을 알아보자.

• 작은 것을 생각하기 : 어떤 알고리즘이 실패한다는 것은 대체로 그것이 실패하는 아주 작은 예제가 있다. 크고 복잡한 사례가 아닌 몇 가지 작은 예제들을 살펴보자. 그건 검증하고 추론하기 쉽다.

• 모든 경우를 생각하기 : n이 작은 값에 대해서는 가능한 경우가 적다. 어떤 구간 두 개가 존재한다면 1. 구간이 disjoint 2. 구간이 겹침 3. 하나가 다른걸 포함 이렇게 3가지 뿐이다. 3 개에 대해서 생각 할 때는 이 3가지 상황에 한개의 구간을 추가하면서 생성하는 것이다.

• 약점을 공략하라 : 제안된 알고리즘이 "항상 가장 큰 것을 취한다"(그리디)는 것과 같은 형태라면 바로 그 부분이 잘못이 있는지 확인한다.

• 동점을 노려라 : 탐욕 휴리스틱을 깨는 바업은 모든 것의 크기가 같은 사례를 제시하는 것이다. 휴리스틱이 결정 할 때 삼는 근거가 갑자기 없어지고, 아마도 최적이지 못한 답으로 출력하게 만들 수 있다.

• 극단을 찾아라 : 반례는 흔히 큰 것과 작은 것, 왼쪽과 오른쪽, 적은 것과 많은 것, 가까운 것과 먼 것의 복합체다. 극단적인 에지 케이스를 잘 고려하자.

반례가 휴리스틱의 정확성을 부정하는 가장 좋은 방법이다.