728x90
본 포스팅은 그림으로 배우는 알고리즘을 참고로 하여 작성되었습니다.
개인 공부를 위한 목적이기 때문에 내용상 오류가 있을 수 있습니다.
1. 알고리즘이란?
- 알고리즘(algorithm)은 컴퓨터를 이용하여 주어진 과제를 해결하기 위한 절차이다.
- 알고리즘에는 ‘정당성’과 ‘정지성’이라는 조건을 충족해야한다.
- 정당성
- 알고리즘은 주어진 과제에 대해 올바른 결과를 반환해야한다.
- 입력값이 지정된 조건과 일치한다면 알고리즘은 반드시 정상적인 동작(올바른 출력값의 반환)을 보장해야한다.
- 알고리즘을 정당성을 증명하는 방법 중 하나는 단정문(Assertion)이 있다.
- 단정문이란 알고리즘은 실행 순서 중 임의의 위치에 서서 충족해야하는 조건이 성립하는지의 여부를 체크하는 것이다.
- 정지성
- 알고리즘은 언젠가 반드시 정지해야만 한다.
- 알고리즘의 정지성이란 어떤한 조건의 입력값이 주어지더라도 정해진 시간 내에 반드시 정상적인 종료를 보장하는 것이다.
- 정당성
2. 알고리즘의 종류
- 기술계산 : 기술 계산을 위한 알고리즘
- 유클리드 호제법(최대공약수)
- 가우스 소거법(방정식)
- 사다리꼴의 법칙(정적분)
- 테이크스트라 알고리즘(최적경로)
- 에라토스테네스의 체(소수)
- 정렬(Sort) : 1줄로 늘어선 데이터를 작은순서(오름차순) 또는 큰 순서(내림차순)로 정렬하는 알고리즘
- 단순 선택정렬
- 단순 교환 정렬(버블정렬)
- 단순 삽입정렬
- 셀 정렬
- 병합 정렬
- 퀵 정렬
- 검색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾아내기 위한 알고리즘
- 선형 검색(리니어 서치)
- 이진 검색(바이너리 서치)
- 문자열 패턴 매칭 : 문자열 중에서 지정한 문자열의 패턴(부분 문자열)과 일치하는 부분을 찾아내기 위한 알고리즘
- 단순 문자열 일치
- KMP 알고리즘
- BM 알고리즘