Algorithm   알고리즘

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

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

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

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


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

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

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


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

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

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


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

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

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

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


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

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


6. 알고리즘의 수행을 위한 기본 절차/구조 셋

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


7. 알고리즘의 분류

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


[알고리즘] 1. 알고리즘 2. 하노이 탑 3. 순서도 4. 재귀 호출
[알고리즘 효율성] [알고리즘 종류] [알고리즘 전략]

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