[알고리즘] 알고리즘이란

알고리즘

문제에 대한 해답을 찾기 위한 체계적인 “문제 해결 절차”

항상 “효율적인 알고리즘”을 고안하는게 중요

최초의 알고리즘 : 유클리드의 최대공약수

알고리즘의 특성

• 정확성 : 주어진 입력에 대한 올바른 해 도출
• 수행성 : 각 단계는 컴퓨터에서 수행 가능해야 한다.
• 유한성 : 무한루프X, 단계를 마친 후 종료되어야 한다.
• 효율성 : 효율적일수록 가치가 높아진다
  • 효율성의 척도 : 시간 복잡도 / 공간 복잡도

정확한 알고리즘

: 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘

정확하지 않은 알고리즘

: 어떤 입력에 대하여 멈추지 않거나 틀린 답을 출력하면서 멈추는 알고리즘

문제의 표기 방법

1. 문제
2. 파라미터 : 문제에서 특정 값이 주어지지 않은 변수
3. 문제의 사례 (입력) : 파라미터에 특정 값 지정
4. 해답 (출력) : 주어진 사례의 질문에 대한 답

문제 표기 예시

1. 문제 : n개의 원소가 있는 목록 S에 x라는 수가 있는지 알아내어 예/아니오로 답하시오.
2. 파라미터 : S, n, x
3. 입력 : S=[1, 4, 6, 9, 12] / n=5 / x=6
4. 출력 : 예

알고리즘 표기

1. 자연어 : 한글 또는 영어 ⇒ 거의 사용하지 않음
2. Pseudo-code (의사 코드)
   • 실제 프로그래밍 언어는 아니지만, 실제 프로그래밍 코드와 비슷하게 과정을 표현
   • 어떤 프로그래밍 언어를 사용하더라도 이해할 수 있는 코드
   • 보통 알고리즘을 표현할 때 주로 사용
3. Flow Chart
   • 도형과 선으로 과정을 표기
   • 장점 : 한 눈에 잘 보인다.
   • 단점 : 복잡한 프로그램에서는 비효율적이다.

알고리즘의 분석

• 입력 데이터 크기가 작을 때
  • 알고리즘 효율이 중요하지 않다
• 입력 데이터가 클 때
  • 알고리즘의 효율성이 굉장히 중요
  • 비효율적인 알고리즘은치명적
  • 점근적 분석 필요