1. Introduction to Algorithms

What is an Algorithm?

알고리즘은 문제를 해결하거나 계산을 수행하기 위한 잘 정의된, 컴퓨터 명령어로 구현가능한 유한한 시퀀스입니다. 한마디로 주어진 input 데이터를 원하는 output 데이터로 만들 수 있는 잘 정의된 계산 과정입니다.

Algorithm is Black Box

혹은, 계산 문제(computational problem)을 해결하는 도구라고 볼 수 있습니다.

 

Characteristics of an algorithm

Input	-
Output	-
Definiteness	Instruction은 clear, unambiguous하다.
Finiteness	유한한 시간 내에 terminate된다.
Effectiveness	Unnecessary하거나 redundant step이 없다.
Independence	프로그래밍 코드에 의존하지 않는다.

 

What is a good algorithm?

좋은 알고리즘인지 판단하기 위한 기준에는 여러가지가 존재합니다.

• Correctness (+Termination)
• The cost of executing the algorithm
  • The amount of time it takes
  • The memory space required to execute the algorithm
  • The amout of power it uses
• Optimality
• Simplicity
• Centralized vs Distributed

 

Analyzing Algorithms and Problems

알고리즘과 문제를 분석하기 위해서 Correctness, Efficiency, Optimality를 분석하고는 합니다. 또한 알고리즘의 효율성(Efficiency)은 Time complexity와 Space complexity로 구분해서 평가합니다. 우선 correctness에 대해 알아봅시다.

 

Correctness

알고리즘을 알게 되면, 가장 먼저 생각해볼 것은 이 알고리즘이 정말로 내가 원하는 목표를 수행하는 지 검증할 필요가 있습니다. 어떻게 이를 검증할까요?

정말 간단하게도, 알고리즘을 구성하는 instructions을 하나하나 따라가면서 확인하면 됩니다. 대신 이렇게 수행할 경우, loop문에서 문제가 생기게 됩니다. 무한히 반복되는 알고리즘의 정확성을 평가하는 것은 이런 방법으로는 한계가 있기 때문입니다. 그래서 증명법을 사용하게 되고, 대표적인 증명법으로서 수학적 귀납법을 사용하게 됩니다.

증명과정은 다음과 같습니다. 알고리즘이 loop를 돌게 되면서 우리가 원하는 한가지 변하지 않는 성질이 있을 것입니다. 이 성질을 loop invariant라고 하는데요, loop invariant이 변하지 않는다고 가정을 하고 증명을 하게 됩니다. 이를 위해서 base 경우, iteration k의 경우에도 그 성질이 성립함을 보이고 iteration k+1에도 만약 그 성질이 변하지 않는다면, 우리는 loop가 loop invariant를 만족하며 동작을 수행하고 있음을 믿을 수 있게 됩니다.

다음의 알고리즘의 correctness를 증명해 봅시다. Largest number를 찾는 알고리즘입니다.

Finding the Largest number

우리는 다음의 Loop invariants를 설정할 수 있습니다.

 

For 1≤ k <n+1, line3의 instruction을 k번 수행하면, ln은 A[1...k] 중 가장 큰 수이다.

 

• Basecase( k=1 )에 대해서, loop invariant는 당연히 성립합니다.
• When k=i에 대해서, loop invariant가 성립한다고 가정합니다. 그러면 k=i+1인 경우, A[i+1]과 ln(A[1...i] 중 가장 큰 수)을 비교해 큰 수를 ln으로 설정하기 때문에, ln은 A[1...i+1] 중 가장 큰 수가 됩니다. 따라서 loop invarinat는 성립하게 됩니다.

이렇게 해서, while문을 지난 후 ln은 A[1...n] 중에서 가장 큰 수가 됩니다. 따라서 주어진 알고리즘의 correctness가 증명됩니다.