알고리즘이란?

알고리즘?
주어진 문제를 해결하기 위한 단계적 절차, 방법

알고리즘의 조건
1. 명확성
알고리즘의 각 단계는 애매모호하지 않고 명확해야 함

2. 정확성
알고리즘은 모든 유효한 입력에 대해 올바른 해를 출력해야 함

3. 정지성
알고리즘은 유효한 입력이 주어지면 반드시 유한한 시간 내에 종료되어야 함

한 가지 문제를 해결하는 알고리즘은 다양, 그 중에서 가장 효율적인 최적의 알고리즘을 선택해야 함

알고리즘적 문제 해결 과정
1. 주어진 문제 완벽하게 이해하기
2. 알고리즘 설계하기
알고리즘 설계 기법들을 참고해서 알고리즘 설계하기

3. 정확성 증명하기
설계한 알고리즘이 모든 유효한 입력에 대해 유한한 시간내에 정확한 결과를 만들어낸다는 것을 증명하기
정확성 증명 방식 중 가장 자주 사용되는 기법: 수학적 귀납법

4. 알고리즘 분석하기
알고리즘의 효율성 분석
시간 효율성: 알고리즘이 얼마나 빨리 실행되는지
공간 효율성: 알고리즘에 따라 작성된 프로그램이 컴퓨터의 메모리를 얼마나 사용하는지
코드 효율성: 알고리즘이 얼마나 이해하기 쉬운지
위의 3가지 효율성을 확인하고 알고리즘이 효율적이지 않은 경우 알고리즘 설계 단계로 되돌아간다.
5. 알고리즘 구현하기
설계한 알고리즘을 프로그램으로 구현
입력의 유효성 검사

알고리즘의 표현 방식
자연어
슈도 코드(의사코드)
프로그래밍 언어

알고리즘 분류
자주 사용하는 주요 알고리즘 설계 기법
분할정복(Divide and Conquer)
동적 계획(Dynamic Programming)
탐욕 기법(Greedy Technique)
되추적(Backtracking)
분기한정(Branch and Bound)

그외 알고리즘 설계 기법
억지 기법: 컴퓨터 성능을 이용해 비효율적 문제해결
무작위 알고리즘: 무작위성(확률)을 이용해 문제 해결
근사 알고리즘: 최적 해에 가까운 해를 찾아 문제해결
병렬 알고리즘: 두개 이상의 CPU를 갖는 병렬 컴퓨터를 최대한 활용하는 알고리즘
분산 알고리즘: 클라우드와 같은 분산컴퓨팅 환경 이용해 문제 해결
양자 알고리즘: 양자 컴퓨터에서 사용하는 알고리즘
유전자 알고리즘: 다윈 진화론의 적자생존 개념을 최적화 문제 해결에 적용

알고리즘을 해결 문제유형에 따른 분류
정렬 알고리즘: 주어진 목록의 항목들 재배열
탐색 알고리즘: 주어진 목록 내 주어진 값을 갖는 항목 찾기
문자열처리 알고리즘: 한 텍스트 내에서 주어진 단어를 찾기
그래프 알고리즘: 그래프로 표현 가능한 문제 해결
조합 알고리즘: 어떤 제약조건들을 만족시키는 조합 객체를 찾아냄
기하학적 알고리즘: 점, 선, 다각형 등 기하학적 객체 다루는 문제 해결
수치 알고리즘: 연속적 성질을 갖는 수학적 객체들 다루는 문제

==========================================

알고리즘의 효율성 분석
시간효율성(시간복잡도), 공간효율성(공간복잡도) 체크하여 효율성 분석
요즘에는 컴퓨터의 발전으로 시간복잡도 분석에 집중
공간복잡도는 꼭 필요한 경우에만 분석