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. 알고리즘의 기본 절차 셋
ㅇ 순차 구조 (Sequence)
ㅇ 선택 구조 (Selection)
ㅇ 반복 구조 (Repetition)
7. 알고리즘의 분류
※ ☞ 알고리즘 분류 참조
- 알고리즘의 주제별 분류 (탐색 알고리즘, 정렬 알고리즘, 그래프 알고리즘 등)
- 알고리즘의 설계 기법/전략/파라다임에 의한 분류 (분할 정복, 동적 프로그래밍 등)
개발/Algorithm