1. 알고리즘이란?

알고리즘(Algorithm)이란?

 ㅇ 알고리즘의 의미

   - 문제를 해결하기 위한 일련의 순서적인 계산/풀이 절차/방법으로, 컴퓨터 프로그램의 작성 시 기초가 된다.

   - 또한 요구되는 해로 이끄는 일련의 단계이지만, 이러한 절차/단계들이 보다 수학적으로 엄격하고 간결하게 다루어질 필요가 있다.

 

 ㅇ 알고리즘의 목적

   - 궁극적으로 문제의 해결을 기계로 실행하기 위한 것

 

알고리즘의 특징

 ㅇ 입력, 출력

   - 입력은 없을 수도 있으나, 출력은 반드시 하나 이상 생성되어야 한다.

 

 ㅇ 유한성( Finiteness )

   - 한정된 수의 작업 후에는, 반드시 유한 시간 내에 종료해야 한다.

 

 ㅇ 명확성( Definiteness )

   - 각 단계는 단순 명확해야 하며, 모호하지 말아야 한다.

 

 ㅇ 유효성( Effectiveness )

   - 모든 명령은 실행 가능해야 한다.

    

 ㅇ 결정성( Determinisim )

   - 매 단계마다, 입력과 바로 전 단계의 결과에 따라 유일하게 결정된다.

 

 ㅇ 일반성( Generality )

   - 특정 입력값들 뿐만 아니라 요구되는 모든 입력에도 적용이 가능해야 한다.

 

 ㅇ 효율성( Efficiency )

   - 알고리즘은 가능한 효율적이여야 한다.

알고리즘 개발의 정형적인 단계

문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화

알고리즘의 분류

 ㅇ 구현

   - 재귀적 알고리즘, 연역적 알고리즘, 결정론적 알고리즘, 근사 알고리즘, 양자 알고리즘 등

 

 ㅇ 설계

   - 무차별 대입 공격, 분할 정복 알고리즘, 그래프 순회, 분기 한정법, 확률적 알고리즘, 리덕션, 백트래킹 등

 

 ㅇ 최적화 문제

   - 선형 계획법, 동적 계획법, 탐욕 알고리즘, 휴리스틱 함수 등

 

 ㅇ 이론적 분야

   - 검색 알고리즘, 정렬 알고리즘, 수치 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 암호학적 알고리즘, 기계 학습, 

데이터 압축 등

 

 

참조사이트

알고리즘 - 위키백과, 우리 모두의 백과사전

알고리즘

 

코딩 테스트 - Level 1 :: #1-1. 알고리즘? | 코드메이트