알고리즘 정의

• 알고리즘이란 문제를 해결하는 단계적 절차 또는 방법

알고리즘의 일반적 특성

• 정확성 : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 함
• 유효성 : 알고리즘의 각 단계는 실제 사람이 또는 컴퓨터가 수행 가능해야 함
• 유한성 : 알고리즘은 유한 시간 내에 종료되어야 한함 (계산 비용, 시간 복잡도)
• 명확성 : 알고리즘에 포함된 모든 명령어들과 절차는 정확하고 명료해야 함
• 효율성 : 주어진 문제를 해결하는 다양한 방법이 있을지라도 보다 적은 계산량과 시간으로 효율적으로 문제를 해결할 수 있는 알고리즘을 고안하는 것이 중요함

알고리즘의 설계와 표현

알고리즘 설계

• 알고리즘이란
  • 어떤 일을 해결하기 위한 방법이나 문제를 해결하기 위한 정차 등을 단계적으로 나열한 것
• 알고리즘 설계란
  • 주어진 문제를 해결하는 방법을 논리적으로 탐구하는 과정
  • 주어진 문제의 특성과 조건, 제한사항 등을 이해하고, 이를 토대로 문제 해결을 위한 다양한 방법과 절차를 논리적으로 도출하며, 실제 그 결과를 확인하는 일련 의 전 과정을 포함

알고리즘 설계의 원칙

• 문제의 정의와 특성을 완벽하게 이해한다
• 해결하려는 문제와 같은(또는 유사한) 유형의 기존 문제들을 해결하는 알고리즘이 존재하는 지 확인하고, 해당 문제에 적용 가능한지 검토한다.
• 주어진 문제를 해결하는 과정이 복잡한 경우, 여러 개의 작은 단위로 나누어 작성 하는 방법을 고려해 본다
• 복잡한 문제를 해결하는 다양한 방법 (문제가 주어지면 어디에 적용이 되는가)
  • 분할 정복법
  • 동적 계획법
  • 그리디 알고리즘
  • 상태 공간 탐색

좋은 알고리즘이란?

• 수행 시간 합리적