프로그램 = 자료구조 + 알고리즘

ex) 최댓값 탐색 프로그램 = 배열 + 순차탐색

자료구조?

접근과 수정을 위해 데이터를 저장하고 정리하는 방법

ex. List, Stack, Queue, Tree, Graph

Correctness of Algorithm

알고리즘이 모든 input instance에 대해 correct output으로 중지되면 correct하다고 한다.

Efficiency of Algorithm

  1. Relative Efficiency

    동일 목적 가진 알고리즘 A와 B의 실행시간, 메모리 사용량 등을 비교

  2. Absolute Efficiency

    주어진 입력 크기에 대해 알고리즘 수행시간이 어떤 함수로 나타나는지 비교

효율적인 알고리즘 예

Greedy Method : 매 단계 가능한 해들 중 가장 좋은 해를 찾는 기법

최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.

어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다.

(예) 물건을 사고 거스름 돈을 동전으로만 받아야 하는 상황에서 가장 적은 수의 동전을 받을 수 있는 방법은? 동전은 500원, 100원, 50원, 10원이 사용된다