- 문제를 해결할 수 있는 잘 정의된(well defined) 유한(finite) 시간 내에 종료되는 계산적인(computational) 절차(procedure)
Ex) 전화번호부에서 "홍길동"의 전화번호 찾기
순차 검색: 첫 페이지부터 "홍길동"이 나올때까지 순서대로 찾는다.
수정된 이분검색: "ㅎ"이 있을 법한 곳으로 넘긴 후 앞뒤로 뒤적이며 찾는다.
-> 첫번째 방법과 두번째 방법을 비교해보면 두번째 방법이 더 효율적이라고 볼 수 있다.
두번째 방법처럼 정렬된 리스트에서 특정 범위를 점점 줄이며 검색하는 방법을 보간검색법(interpolation search)라고 한다.
알고리즘의 표기
1. 자연어: 한글 또는 영어
- 우리가 평소에 사용하는 말로 표현한 것
- 해석하는 사람에 따라 다르게 해석할 가능성이 존재한다.
- 상대적으로 긴 문장이 필요하다.
2. 프로그래밍 언어: C, C++, Java, ML 등
- 한 눈에 알고리즘을 파악하는 데에 어려움이 존재한다.
3. 의사코드: pseudo-code
- 직접 실행할 수 있는 프로그래밍 언어는 아니지만, 거의 실제 프로그램에 가깝게 계산과정을 표현할 수 있다.
- 간결하고 정확한 의미 전달이 가능하다.
4. 흐름도
- 도형과 화살표를 통해 알고리즘의 흐름을 한 눈에 볼 수 있도록 표기한다.
심벌 이름
도형
내용
터미널 심벌
흐름도의 시작과 끝을 나타내는 기호
입출력 심벌
입출력 작업 표시
프로세스 심벌
연산 명령문 등 처리해야 할 작업 내용
판단 심벌
조건과 판단
연결 심벌
페이지 내, 외의 연결
미리 정의된 프로세스 심벌
모듈, 함수, 메소드, 하위절차
흐름 심벌
연결 흐름 표시
준비 심벌
변수의 초기화
문서 출력 심벌
문서로 출력
데이터베이스 심벌
데이터베이스
예시
[문제] 배열(a[]) 안에 있는 10개의 데이터에서 제일 큰 수를 찾아라.
5
3
8
2
9
4
7
1
0
6
1. 자연어(natural language) 배열 안의 첫 데이터를 최댓값 M으로 설정한다. 오른쪽으로 이동하면서 해당 데이터와 M을 비교하여 해당 데이터가 더 크면 그 데이터를 M으로 재설정한다. 작다면 다음으로 이동한다. 배열의 끝에 도달하면 M이 데이터의 최댓값이 된다.
2. 의사코드(pseudo code) (1) 1: a[0]의 데이터를 최댓값 M으로 설정 2: a[1]과 M 비교 후 a[1]이 더 크면 M 재설정, 아니면 a[2] 비교로 이동 3: 2단계를 배열의 끝까지 수행 4: M이 데이터의 최댓값 (2) M = a[0] for each a[i], 1 <= i <= 9 if a[i] > M then M = a[i] fi end for M is maximum
3. 흐름도(flow chart)
4. 프로그래밍 언어(programming language)
void main(){
int i, a[10] = {5, 3, 8, 2, 9, 4, 7, 1, 0, 6};
int M;
M = a[0];
for (i = 1; i <= 9; i++)
if (a[i] > M)
M = a[i];
cout << M;
}
