알고리즘이란

알고리즘

알고리즘은 문제를 해결하기 위한 단계를 체계적으로 명시한 것을 의미한다.

• 문제를 해결하기 위한 것
• 명확하게 정의
• 순서가 있는 유한 개의 규칙으로 이루어진 작업

 

알고리즘의 조건

• 입력: 외부에서 제공되는 자료가 0개 이상 존재한다.
• 출력: 적어도 2개 이상의 서로 다른 결과를 내어야 한다. (모든 입력에서 하나의 출력만 나오면 안됨)
• 명확성: 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
• 유한성(종결성): 유한 개의 명령어를 수행한 후(유한 시간 내) 종료되어야 한다.
• 효율성: 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

 

알고리즘 연구 분야

• 고안: 완벽한 자동화를 통한 알고리즘의 개발은 불가능하므로 이미 증명된 유용한 알고리즘들을 습득함으로써 보다 유용한 알고리즘을 개발하는데 의미가 있다.
• 검증: 고안된 알고리즘이 합당한 입력값에 대하여 올바른 결과를 계산해내는지를 밝히는 절차가 필요하다. 알고리즘 검증은 고안된 알고리즘이 프로그래밍 언어와 독립적으로 올바르게 작동할 수 있음을 보여주는데 목적이 있다.
• 분석: 고안된 알고리즘을 실행하기 위해 필요한 실행 시간과 필요로 하는 기억 장치를 결정하는 것이다.
• 테스트: 디버깅, 성능 분석

 

좋은 알고리즘의 분석 기준

• 정확성: 적당한 입력에 대해 유한 시간 내 올바른 답을 산출하는가를 판단한다.
• 작업량: 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정하고, 해결하고자 하는 문제의 중요 연산이 여러 개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산한다.
• 기억 장소 사용량: 수행에 필요한 저장 공간
• 최적성: 어떤 알고리즘보다 더 적은 연산을 수행하는 알고리즘이 있는지 찾아 최적의 기법을 사용한다.
• 복잡도: 시간 복잡도, 공간 복잡도