알고리즘 개념

알고리즘 정의

알고리즘이란 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다.

 

 

알고리즘의 조건

알고리즘은 다음의 조건을 만족해야 한다.

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

 

 

알고리즘의 구현 단계

문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화

 

 

알고리즘 예시

다음은 가장 큰 숫자를 찾는 알고리즘이다.

알고리즘 LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.

  if L.size = 0 return null
  largest ← L[0]
  for each item in L, do
    if item > largest, then
      largest ← item
  return largest

• "←"은 대입을 가리킨다. 이를테면 "α ← β"는 α에 β를 대입하는 것을 뜻한다.
• "return"은 알고리즘을 종료하고 다음의 값을 출력한다.

 

 

좋은 알고리즘의 분석 기준

• 정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.
• 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산
• 기억 장소 사용량 : 수행에 필요한 저장 공간
• 최적성 :그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 '가장 좋은'의 의미이다
• 복잡도. (점근 표기법 : Big-O Notation)

• O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
• O(log N) : 입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다.
• O(N) : 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.
• O(N log N) : 입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다.
• O(N2) : 입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가진다.
• O(N3) : 입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가진다.
• O(2n) : 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다.
• O(n!) : 입력 자료의 크기가 N일경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. ex)외판원 문제(TSP)의 기본적인 해법