Algorithm   알고리즘

(2020-03-03)
1. 알고리즘 (Algorithm) 이란?

  ㅇ 알고리즘의 의미
     - 문제를 해결하기 위한 일련의 순서적인 계산/풀이 절차/방법 (문제 풀이 과정)
        . 이는 컴퓨터 프로그램(일련의 잘 정의된 명령어들의 집합)의 작성시 기초가 됨
     - 또한, 요구되는 해로 이끄는 일련의 단계 (프로시져)
        . 다만, 이러한 절차/단계들이 보다 수학적으로 엄격하게 간결하게 다루어질 필요 있음

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

  ㅇ 알고리즘의 어원
     - 9세기경 아라비아의 천문학자,수학자인 알고리즈미(al-Khowarizmi)의 이름에서 유래
        . 십진법에 의해 덧셈,뺄셈,곱셈.나눗셈,제곱근,원주율을 구하는 방법을 아랍어로 기록


2. 알고리즘의 특징

  ㅇ (입력,출력)             입력은 없을수도 있으나, 출력은 반드시 하나 이상 생성되어야함
  ㅇ (유한성, Finiteness)    한정된 수의 작업 후에는, 반드시 유한 시간 내에 종료해야 함 
  ㅇ (명확성, Definiteness)  각 단계는 단순 명확해야하며, 모호하지 말아야 함 
  ㅇ (유효성, Effectiveness) 모든 명령들은 실행가능해야 함 
  ※ 이상의 것들은, 미국 스탠포드대학 Knuth 교수가 제시 함 ("The Art of Computer Programming")

  ㅇ (일반성, Generality)    특정 입력값들 만 아니라 요구되는 모든 입력에도 적용 가능 
  ㅇ (효율성, Efficiency)    알고리즘은 가능한 효율적이어야 함


3. 알고리즘의 표현

  ㅇ 알고리즘의 표현
     - 문제를 해결하는 과정을 기술하는 수단으로써, 알고리즘을 표현할 때,
     - 일상 언어,의사코드,흐름도(순서도),프로그래밍 언어(C 언어 등) 등 다양하게 사용 가능

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


4. 알고리즘의 분석 : `효율성/성능` 분석

  ※ [참고] ☞ 알고리즘 효율성 참조

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

  ㅇ 효율성 구분
     - 소요 계산 시간 (연산 수) : 시간 복잡도 (Time Complexity)
     - 소요 메모리 : 공간 복잡도 (Space Complexity)

  ㅇ 효율성 분석
     - 문제의 입력 크기가 증가함에 따라, 
     - 처리 시간(연산 수) 및 소요 메모리가 얼마나 증가하는가를 분석함


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

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


6. 알고리즘의 수행 구조 셋

  ※ ☞ 제어 구조 참조
     - 알고리즘에 담겨진 논리를 표현하며 처리 흐름의 제어를 가능케 하는 구조 셋
        . 순차 구조, 선택 구조, 반복 구조


7. 알고리즘의 분류

  ※ ☞ 알고리즘 분류 참조
     - 알고리즘의 주제별 분류
        . 탐색 알고리즘 (선형검색,이진검색 등)
        . 정렬 알고리즘 (버블정렬,선택정렬,삽입정렬 등)
        . 그래프 알고리즘 등
     - 알고리즘의 설계 기법/전략/패러다임에 의한 분류
        . (분할 정복, 탐욕 알고리즘, 동적 프로그래밍 등)


[알고리즘] 1. 알고리즘 2. 순서도 3. 재귀 호출
[알고리즘 효율성] [알고리즘 종류] [알고리즘 전략] [(기타 알고리즘)]
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 순서도
            3. 재귀 호출
        1.   알고리즘 효율성
        2.   알고리즘 종류
        3.   알고리즘 전략
        4.   (기타 알고리즘)
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     요약목록     참고문헌