알고리즘을 생각해보자

하노이의 탑으로 알고리즘을 생각

• 원반 3장을 최단 경로로 옮기는 알고리즘 생각

알고리즘이 만족해야하는 조건

1) 범용성, 정당성, 결정성

• 범용성은 작업자와 상관없이 어떤 환경에서도 같은 결과를 내어야 올바른 알고리즘
• 정당성은 주어진 과제에 대해 올바른 결과, 출력을 얻을 수 있어야 올바른 알고리즘
• 같은 입력 시 반드시 같은 결과가 나와야 올바른 알고리즘

Tip, 알고리즘 용어

• 문제: 알고리즘 해결하려는 내용
• 프로그램 : 알고리즘을 컴퓨터에 실행하기 위해 프로그래밍 언어로 써낸 것
• 입력 : 알고리즘 처리 대상이 되는 데이터
• 출력 : 알고리즘을 실행해서 얻은 결과
• 스텝 : 알고리즘을 구성하는 절차, 복잡하거나 시간 걸리는 알고리즘일 수록 스텝 수 증가
• 최적화 : 알고리즘의 스텝수나 처리 시간 줄여 효율적 처리하도록 개선

2) 유한성

• 알고리즘은 유한성 역시 만족해야함
• 무한으로 반복하는 절차는 문제 해결 할 수 없기에

3) 정지성

• 알고리즘은 언제가 정지해야한다. 그러나 정지 여부를 판정하는 알고리즘은 만들 수 없다.

알고리즘의 실행 시간

알고리즘 실행 시간 판단 위해 '계산량' 지표 사용

• 계산량이란 시간 계산량과 공간 계산량으로 나눔
  - 시간은 얼마만큼의 처리 시간이 필요한지, 공간은 어느정동의 기억 용량, 즉 메모리가 필요한지를 의미
  
• 알고리즘의 계산량은 걸리는 시간을 뜻하는 게 아니라 스텝의 개수(명령 갯수)를 기준으로 한다. 환경에 따라 스텝 실행에 따른 시간은 바뀌지만 개수는 바뀌지 않기에

조합적 확산

• 처리할 데이터 조합이 방대해져 스텝의 개수가 너무 많아지는 경우
• 조합적 확산이 일어날 때는 다른 알고리즘 사용해 현실적인 시간 내 문제 해결

정리

• 알고리즘 문제풀기 위한 절차
• 알고리즘 주어진 입력에 필요한 출력을 얻는 방법을 간단한 조작이나 절차를 조합해서 명확히 정의
• 프로그램은 프로그래밍 언어로 쓰여진 알고리즘 작업 지시서
• 알고리즘은 범용성, 정당성, 결정성, 유한성, 정지성 갖춰야함
• 조합적 확산일어나면 실행 시간이 엄청걸림
• 알고리즘은 정지해야함