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. 일고리즘 분류
  1.   기술공통
  2.   기초과학
  3.   파동/광학/음향
  4.   방송/멀티미디어/정보이론
  5.   전자/전기/제어
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
      1.   프로그래밍 언어론
      2.   객체지향
      3.   자료구조
      4.   알고리즘
        1.   1. 알고리즘
            2. 알고리즘 설계
            3. 계산 복잡도
            4. 정렬 알고리즘
            5. 탐색 알고리즘
            6. 그래프 알고리즘
            7. 해쉬 알고리즘
            8. 해싱 탐색
            9. 하노이 탑
            10. 일고리즘 분류
      5.   자료표현(알파벳/코드)
      6.   시스템 프로그래밍
      7.   프로그래밍언어 종류
      8.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   기계/재료/공업일반
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     참고문헌