[Algorithm] Basics 2

 

반례를 찾을 수 없다 ≠ 좋은 알고리즘이다

우리는 어떠한 명제가 자명하다는 사실을 증명을 통해 밝혀내야 한다. 대표적인 방법으로는 Induction이 있다.

 

Induction Principle

수학적 귀납법의 원리를 따른다.

 

1. State that the proof uses induction

- induction을 이용하여 증명할 것을 명시

2. Define an appropriate predicate P(n)

- 최종적으로 증명할 명제를 명시

3. Prove that P(0) is true

- 이 시작점을 우리는 Base case or Basis step이라고 부름

4. Prove that P(n) implies P(n+1) for every natural number n

- 이걸 inductive step or induction step이라고 부름

5. Invoke induction

- P(n)이 결과적으로 모든 자연수 n에 대해 만족하다고 결론을 내린다.

 

Data structures?

- 알고리즘 공부에 있어서 자료 구조는 매우 중요한 역할을 한다.

- 데이터의 접근과 수정이 용이하게 하기 위함

- 데이터를 조직하고 저장하기 위한 방법론

- 한가지 데이터로 모든 목적을 도달할 수 없음

- 각각의 데이터 구조의 장단점을 알면 특정 목표에 걸맞게 적절하게 사용할 수 있음.

 

Hard problems

효율적인 알고리즘을 다루는 게 알고리즘 과목 내용의 대부분을 차지하지만, 효율적인 해결법이 없는 문제들도 여럿 존재한다. 어떤 해결법이 효율적인가를 알 수 없는 경우, 우리는 그것들을 NP-complete라고 한다.

 

왜 NP-complete problems가 흥미로울까? 그 이유는

 

"이 문제에 대해 효율적인 알고리즘이 존재하지 않는다"라는 것을 밝혀낸 사람이 아무도 없기 때문이다.

그리고 이들은 실제로 NP-complete problem이 아닌 문제들과 비슷할 때도 있기 때문에 구별이 쉽지가 않다.

만약 이러한 종류의 문제들 중에 효율적인 알고리즘이 하나라도 존재한다면, 모든 문제에 대한 효율적인 알고리즘이 존재하게 된다.

 

hard problems의 예로는 대표적으로 Traveling-salesman problem (TSP)가 있다.

 

Efficiency

효율성이란 알고리즘에 있어서 중요한 요소이다. 예를 들어 Insertion sort는 시간 복잡도가 n²에 해당되고, Merge sort는 n · log n의 시간 복잡도를 가진다. 따라서 input size가 그리 크지 않다면, 이들의 시간 복잡도에서 계수가 큰 역할을 하여 Insertion sort가 더 빠를 수 있지만, input size가 매우 크다면 앞에 붙은 계수는 그리 큰 영향을 미치지 못하게 되어 결국 Merge sort가 더 빠르게 작동할 수 있다.

 

어떠한 상황에 어떤 알고리즘을 사용해야 하는지를 아는 것은 중요한 요소다. 컴퓨터 하드웨어가 빠른 것만큼이나 효율적인 알고리즘을 고르는 것 또한 시스템의 성능에 큰 영향을 미치기 때문이다.