(CS50)-알고리즘 기초(알고리즘)

CS50 x edwith 강의를 들으며 정리한 공부 포스팅입니다.

그림출처

핵심 개념

• 알고리즘
• 정확성
• 효율성

알고리즘

• 입력에서 받은 자료를 출력형태로 만드는 처리 과정
• 즉, 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한
• 규칙들의 순서적 나열

예제: 전화번호부에서 Mike Smith를 찾는다.

정확한 알고리즘(정확성)

• 전화번호부에서 Mike Smith를 찾을 때까지 처음부터 끝까지 찾는것을 반복.
• Mike Smith가 없는 경우를 제외하면 이 알고리즘은 정확하다.
• 효율적이지 않은것이 단점.

효율적인 알고리즘(효율성)

• 책을 절반씩 펼쳐 한 페이지가 남아 Mike Smith가 있는지 없는지를 찾고 끝낸다.
• 효율성: 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일수 있는지에 대한 척도.
• 알고리즘은 정확성도 중요하지만 효율성도 중요함.
• 위의 정확한 알고리즘보다 더 효율적임.
  • 만약 500페이지가 추가되었다고 가정한다면
  • 첫번째 알고리즘은 같은 절차를 500번 더 수행될것이지만
  • 두번째 알고리즘은 단 1번만 추가로 수행하면 되기 때문.