Algorithm   알고리즘

(2017-12-04)
1. 알고리즘 이란?

  ㅇ 알고리즘 (Algorithm)
     - 문제를 해결하기 위한 일련의 순서적인 계산/풀이 절차
        . 이는 컴퓨터 프로그램(일련의 명령어들의 집합)의 작성시 기초가 됨
     - 요구되는 해로 이끄는 일련의 단계(프로시져)

  ㅇ 알고리즘의 목적
     - 궁극적으로 문제의 해결을 기계로 실행하기 위한 것

  ㅇ 알고리즘의 어원
     - 9세기경 아라비아의 천문학자,수학자인 알고리즈미(al-Khowarizmi)의 이름에서 유래


2. 알고리즘의 특징/조건

  ㅇ (입력,출력)             입력은 없을수도 있으나, 출력은 반드시 하나 이상 생성되어야함
  ㅇ (유한성,Finiteness)     한정된 수의 작업 후에는 반드시 종료해야 함 
  ㅇ (명확성, Definiteness)  각 단계는 단순 명확해야하며, 모호하지 말아야 함 
  ㅇ (유효성, Effectiveness) 모든 명령들은 실행가능해야 함 
  ㅇ (일반성,Generaliy)      특정 입력값들 만 아니라 요구되는 형태의 모든 문제에 적용가능 


3. 알고리즘의 기술(記述)/표현

  ㅇ 알고리즘의 표현
     - 일상 언어, 의사코드, 흐름도, 프로그래밍 언어(C 언어 등) 등 다양하게 표현이 가능

  ㅇ 보통, 의사코드(Pseudocode)를 많이 사용
     - 자연 언어도 아니고, 특정 프로그래밍 언어도 아닌 그 중간 단계의 언어로써,
        . 형식적이고 명확한 문장과 제어 구조는 지니나, 상세 구현 레벨까지는 신경을 쓰지 않음


4. 알고리즘의 `효율성(Efficiency)` 분석

  ㅇ 컴퓨팅 자원의 한계성
     - 계산 시간 및 메모리 비용 모두가 한정된 자원이므로,
     - 효율적 알고리즘이 필요하고, 그 효율성을 분석 평가할 척도도 필요함

  ㅇ 효율성 구분
     - 계산 시간   : 시간 복잡도 (Time Complexity)
        . 주로, 알고리즘이 사용한 연산의 수
           .. 주요 기본 연산 : 정수의 비교,덧셈,곱셈,나눗셈 등
     - 소요 메모리 : 공간 복잡도 (Space Complexity)
        . 소요되는 컴퓨터 메모리

  ㅇ 효율성 척도 : 계산 복잡도 (Computational Complexity,Complexity Metric)
     - 주로, 시간복잡도를 대상을 함

  ㅇ 분석 대상
     - 문제의 크기(입력 크기)가 증가함에 따라, 처리 시간/소요 메모리가 얼마나 증가하는가
     - 입력 크기 例)
        . 배열의 크기, 다항식 차수, 행렬의 항목 수, 이진 입력 비트 수,
          그래프에서 정점 및 가지 등
     - 즉, 수행 시간을 입력 크기 n에 따른 함수 f(n)으로 표현 가능
        . 이는 기계적인 속도나 프로그래밍 스타일과는 무관함


5. 알고리즘의 `정확성(Correctness)` 분석

  ㅇ 알고리즘이 기대한대로 항상 올바른 결과를 내는지 증명하는 것


6. 알고리즘의 분류

  ※ ☞ 알고리즘 분류 참조
     - 알고리즘의 주제별 분류 (탐색 알고리즘, 정렬 알고리즘, 그래프 알고리즘 등)
     - 알고리즘의 설계 기법/전략/파라다임에 의한 분류 (분할 정복, 동적 프로그래밍 등)


[알고리즘] 1. 알고리즘 2. 알고리즘 설계 3. 계산 복잡도 4. 정렬 알고리즘 5. 탐색 알고리즘 6. 그래프 알고리즘 7. 해쉬 알고리즘 8. 해싱 탐색 9. 하노이 탑 10. 일고리즘 분류

 
        최근수정     참고문헌