2. 알고리즘

이전에 썼던 1. 자료구조 내용의 연장이다. 내용이 길어서 나눠서 정리하게 되었다.

 

알고리즘이란 쉽게 말하면 문제를 해결할 수 있는 방법이다. 컴퓨터를 이용하여 전화번호부에서 특정한 사람의 이름을 찾는다고 할 때, 한 가지 방법은 전화번호부의 첫 페이지부터 시작하여 한 장씩 넘기면서 특정한 사람을 찾는 것이다.

 

이 방법은 엄청난 시간이 걸리는 방법이고 보통 이런식으로 찾는 사람은 거의 없을 것이다. 또 하나의 방법은 전화번호부의 이름들이 정렬되어 있음을 이용하는 방법이다. 즉 찾고자 하는 이름이 "박철수"라고 할 때 전화번호부의 중간에 있는 이름과 "박철수"를 비교한다. 중간에 있는 이름보다 앞에 있다면 앞부분만 검색하고 그렇지 않다면 뒷부분만 검색하면 된다. 이 방법은 굉장히 효율적인 방법이고 일반적인 사람들이 사용하는 방법이다. 나중에 배우겠지만 이러한 방식을 이분탐색 알고리즘이라고 한다. 이러한 방법들은 보통 프로그래밍 스타일이나 프로그래밍 언어와는 무관하다. 

 

즉, C언어를 사용하건, Java를 사용하건, 사용되는 방법은 동일하다.

 

두 번째로 해야 할 일은 이들 방법에 따라 컴퓨터가 수행하여야 할 단계적인 절차를 자세히 기술하는 것이다. 컴퓨터로 문제를 풀기 위한 단계적인 절차를 알고리즘이라고 한다. 엄밀하게 이야기하면 알고리즘이란 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것이다. 따라서 알고리즘은 특정한 일을 수행하는 명령어들의 집합이라고 할 수 있다. 여기서 명령어란, 컴퓨터에서 수행되는 문장들을 의미한다.

 

모든 명령어들의 집합이 알고리즘이 되는 것은 아니고 알고리즘이 되기 위한 조건들을 만족하는 집합만이 알고리즘으로 정의된다. 

알고리즘의 정의

입 력	0개 이상의 입력이 존재하여야 한다.
출 력	1개 이상의 출력이 존재하여야 한다.
명백성	각 명령어의 의미는 모호하지 않고 명확해야 한다.
유한성	한정된 수의 단계 후에는 반드시 종료되어야 한다.
유효성	각 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 한다.

따라서 알고리즘에는 입력은 없어도 되지만 출력은 반드시 하나이상 있어야 하고 모호한 방법으로 기술된 명령어들의 집합은 알고리즘이라 할 수 없다. 또한 실행할 수 없는 명령어(예를 들면 0으로 나누는 연산)을 사용하면 역시 알고리즘이 아니다. 또한 무한히 반복되는 명령어들의 집합도 알고리즘이 아니다.

 

알고리즘을 기술하는 4가지 방법

1. 한글이나 영어 같은 자연어
2. 흐름도
3. 의사 코드
4. 프로그래밍 언어

가장 많이 쓰이는 방법은 3,4와 같은 의사 코드나 프로그래밍 언어를 사용하는 방법이다.

프로그래밍 언어의 예약어들은 모두 명백한 의미를 가지고 있어서 알고리즘을 기술하는데 안성맞춤이다. 

의사코드는 자연어보다는 더 체계적이고 프로그래밍 언어보다는 덜 엄격한 언어로서 알고리즘을 기술하는 데만 사용되는 코드를 말한다.