[Algorithm] Basics 1

Algorithm

좋은 알고리즘의 특성

1. Correct

2. Efficient

3. Easy to implement

 

이 순서대로 중요하게 여기고, 이 세가지를 동시에 만족시키지 못할 수도 있음.

 

Collect algorithm?

- 모든 input에 대해 정확한 output에 멈춰야 한다.

- 프로그램이 멈추지 않거나, 오답에서 멈춘다면 옳은 알고리즘이 아님.

- 가끔 incorrect algorithm이 유용하게 쓰일 데가 있음! → Error rate 제어가 가능하다면

- Correct vs Incorrect를 구별하려면 Proof가 필요

 

Correctness를 증명하려면

입력 가능한 instance를 명확히 알아야 하고.

알고리즘의 출력값의 요구되는 특성을 명확히 알아야 함.

 

문제에 대한 오류

애매한 것을 요구한다!

"the best route between two places on a map"

→ best가 의미하는 바를 모름

 

복합적인 목표를 요구한다!

"find the shortest path from a to b that doesn't use more than twice as many turns as necessary"

→ 잘 정의되었지만 이해하고 풀기 복잡함

 

Incorrectness를 증명하려면 → 좋은 반례가 필요

좋은 반례의 특징은

1. Verifiability (확인 가능성)

→ 특정 입력에 대해서 알고리즘이 예상대로 잘 작동하는지 확인할 수 있어야 함

2. Simplicity (간결함)

→ 왜 이 알고리즘이 실패했는지 정확히 설명할 수 있어야 함

 

알고리즘이 특정 상황에서 작동하지 않거나 (그런 약점을 찾거나) → Hunt for the weakness

특정 상황에서 예측 가능한 결과를 만들지 못하거나 → Go for a tie

입력의 극단적인 상황을 찾아내거나 → Seek extremes

 

Expressing alogrithms

- English

- A real programming language

- Pseudocode → 위 두 언어의 장점을 합친 것

 

Review Point

1. Correct algorithm을 뭐라고 정의할 수 있는가?

2. Counter-example이란 무엇인가?