알고리즘과 자료구조 초보자

알고리즘을 안다는 것은 특정 알고리즘이 존재한다는 것을 알고 있을 뿐만 아니라, 언제 적절히 사용할 수 있는 것인지를 아는 것을 말한다.

 

문제를 작은 단위로 쪼개어서 최적의 알고리즘을 찾아내는데, 이때 하는 것을 알고리즘식 생각 혹은 "Algorithmic Thinking" 이라고 표현한다.

 

알고리즘의 속성

1. 명확히 정의된 문제와 입력값, 출력값

2. 알고리즘의 프로세스는 매우 구체적인 단계로 이루어져 있다.

3. 그 단계들 역시 명확히 구분되어야 한다.

4. 알고리즘은 결과값을 출력해야 한다.

5. 제한된 시간 내에 완수해야 한다.

 

 

좋은 알고리즘의 속성

옳음Correctness :

1. 문제와 입력과 출력이 정확히 정의되어 있다. 인풋값에 어떤 값을 넣어도 정확한 답을 얻을 수 있다.

2. 문제를 해결하고서 알고리즘은 반드시 끝이 나야 한다.

 

위 두 가지 속성을 만족시키지 못한다면 알고리즘은 옳지 않다고 표현한다. 알고리즘의 옳음에 관한 서적을 읽어보면 수학적 증명을 많이 만나게 되는데, 알고리즘의 옳음의 영역은 원래 수학적 귀납의 영역이었기 때문이다.

 

효율Efficiency :

1. 시간복잡도

임무를 완성하는데 얼마나 걸리는가?

 

2. 공간복잡도

메모리의 사용의 정도