1장 알고리즘이란

알고리즘 (Algorithm)은 컴퓨터를 이용하여 주어진 과제를 해결하기 위한 처리 절차.
= 문제 해결을 위한 처리 절차

• 선인들의 지혜가 담긴 프로그램의 본보기
• 알고리즘을 학습하면 질 좋은 프로그램을 만들 수 있다.
• 알고리즘의 학습은 게임 공략법 같은 것
• 알고리즘은 더 나은 프로그램을 만들기 위한 ‘정석’이다.

알고리즘에는 ‘정당성’과 ‘정지성’이 있어야 한다.

• 정당성: 입력값이 지정된 조건과 일치한다면 알고리즘은 반드시 정상적인 동작 (올바른 출력값의 반환)을 보장해야 한다.
• 정지성: 어떠한 조건의 입력값이 주어지더라도 정해진 시간 내에 반드시 정상적인 종료를 보장하는 것.

알고리즘의 종류

기술 계산

• 유클리드 호제법 (최대공약수)
• 가우스 소거법 (방정식)
• 사다리꼴의 법칙 (정적분)
• 데이크스트라 알고리즘 (최적경로)
• 에라토스테네스의 체 (소수)

정렬

• 단순 선택 정렬
• 단순 교환 정렬 (버블정렬)
• 단순 삽입 정렬
• 셸 정렬
• 병합 정렬
• 퀵 정렬

검색 (Serch)

• 선형검색 (리니어 서치)
• 이진 검색 (바이너리 서치)

문자열 패턴 매칭

• 단순 문자열 일치
• KMP 알고리즘
• BM 알고리즘