1. 알고리즘 (Algorithm) 이란?
ㅇ (의미)
- 문제를 해결하기 위한 일련의 순서적인 계산/풀이를 정해놓은 절차/방법 : (문제 풀이 과정)
. 입력을 받아 정해진 규칙에 따라 처리하여 원하는 출력을 도출하는 과정
- 또한, 요구되는 해로 이끄는 일련의 단계 : (프로시져)
. 이 단계들은 모호하지 않고, 누구나 동일한 결과를 얻도록 정확하고 수학적으로 엄격해야 함
- 또한, 문제를 해결하기 위한 사고법 및 그 절차 : (생각의 흐름을 구조화한 것)
ㅇ (목적)
- 궁극적으로, 문제의 해결을 기계로 실행하기 위한 것
ㅇ (용도)
- 알고리즘은, 컴퓨터 프로그램(일련의 잘 정의된 명령어 집합)의 작성에 기초가 되며,
. 효율적인 자료 처리, 최적화된 자원 사용, 자동화된 문제 해결을 가능하게 함
ㅇ (어원)
- 9세기경 아라비아의 천문학자,수학자인 알고리즈미(al-Khowarizmi)의 이름에서 유래
. 십진법에 의해 덧셈,뺄셈,곱셈.나눗셈,제곱근,원주율을 구하는 방법을 아랍어로 기록
2. 알고리즘의 특징
ㅇ (입력,출력) : 입력은 없을수도 있으나, 출력은 반드시 하나 이상 생성되어야함
ㅇ (유한성, Finiteness) : 한정된 수의 작업 후에는, 반드시 유한 시간 내에 종료해야 함
ㅇ (명확성, Definiteness) : 각 단계는 단순 명확해야하며, 모호하지 말아야 함
ㅇ (유효성, Effectiveness) : 모든 명령들은 컴퓨터에서 실행가능해야 함
※ 이상의 것들은, 미국 스탠포드대학 Knuth 교수가 제시 함 ("The Art of Computer Programming")
ㅇ (결정성, Determinisim) : 매 단계 마다, 입력과 바로 전 단계의 결과에 따라 유일하게 결정됨
ㅇ (일반성, Generality) : 특정 입력값들 만 아니라 요구되는 모든 입력에도 적용 가능
ㅇ (효율성, Efficiency) : 자원과 시간을 가능한 최소로 사용해야 함
3. 알고리즘의 표현
ㅇ 알고리즘의 표현 수단
- 문제 해결 과정을 기술하는 수단으로써, 알고리즘을 표현할 때, ☞ 알고리즘 도식화 참조
- 일상 언어, 의사코드, 흐름도(순서도), 프로그래밍 언어(C 언어 등) 등 다양하게 사용 가능
ㅇ 보통, 의사코드(Pseudocode)를 많이 사용
- 자연 언어도 아니고, 특정 프로그래밍 언어도 아닌 그 중간 단계의 언어로써,
- 제어 구조와 문장은 형식적으로 명확하되, 구현 세부사항은 생략
4. 알고리즘의 분석 : `효율성/성능` 분석
※ [참고] ☞ 알고리즘 효율성 참조
ㅇ 컴퓨팅 자원(시간,메모리)의 한계로 인해, 효율적 알고리즘 필요
- 이에따라, 그 효율성을 분석 평가할 척도도 필요함
ㅇ 효율성 구분
- 소요 계산 시간 (연산 수) : 시간 복잡도 (Time Complexity)
- 소요 메모리 : 공간 복잡도 (Space Complexity)
ㅇ 효율성 분석
- 문제의 입력 크기가 증가함에 따라,
- 처리 시간(연산 수) 및 소요 메모리가, 얼마나 증가하는가를 분석함
5. 알고리즘의 분석 : `정확성(Correctness)` 분석
ㅇ 알고리즘이 항상 올바른 결과를 내는지를 수학적으로 증명하는 것
6. 알고리즘의 수행 구조 셋
※ ☞ 제어 구조 참조
- 알고리즘에 담겨진 논리를 표현하며, 처리 흐름의 제어를 가능케 하는 구조 셋
. 순차 구조, 선택 구조, 반복 구조
7. 알고리즘의 분류
※ ☞ 알고리즘 분류 참조
- 알고리즘의 주제별 분류
. 기초 알고리즘 (유클리드 알고리즘 등)
. 선택 알고리즘 (`순위 찾기` 등)
. 탐색 알고리즘 (선형검색, 이진검색 등)
. 정렬 알고리즘 (버블정렬, 선택정렬, 삽입정렬 등)
. 그래프 알고리즘 (그래프 순회, 최단 경로 등)
. 최적화 알고리즘 (선형계획법, 유전 알고리즘, 경사하강법 등)
- 알고리즘의 설계 기법(전략,패러다임)별 분류
. 분할 정복 (병합정렬, 퀵정렬 등)
. 탐욕 알고리즘 (최소비용신장트리, 거스름돈 문제, 배낭 문제 등)
. 동적 프로그래밍 (피보나치 수열 등)
. 백트래킹 (미로찾기, 색칠문제 등)