컴퓨팅은 입력(input)을 받아 그 입력을 처리한 후 출력(output)하는 과정이다. 알고리즘(Algorythm)은 입력에서 받은 자료를 출력 형태로 처리하는 그 중간 과정을 뜻한다.
즉, 알고리즘은 출력값으로의 과정이라고 볼 수 있으며 입력된 값으로 특정 출력값을 얻기 위해 어떤 명령들이 수행돼야 하는지에 관한 것을 규칙으로 만들고 그 규칙을 '순서적으로 나열'하는 것이다.
이러한 일련의 순서적 규칙들을 어떻게 나열하는지에 따라 알고리즘이 달라질 것이다.
1. 정확한 알고리즘: 첫 페이지부터 찾기
예를 들어, 전화번호부에서 'Mike Smith'를 찾는 일을 한다고 하자.
가장 생각하기 쉬운 방법은 처음부터 찾기다.
1 전화번호부에서 첫 페이지를 펼친 후 Mike Smith가 그 페이지에 있는지 찾는다.
2 Mike Smith가 없으면, 그 다음 페이지에서 찾는다.
3 Mike Smith를 찾을 때까지 혹은 전화번호부가 끝날 때까지 이짓(?)을 반복한다.눈이랑 손이 아프긴 하겠지만 언젠가는 Mike Smith를 찾을 수 있는 방법이다.
(Mike Smith가 전화번호부에 있다면..!)
하지만 처음부터 찾기 알고리즘은 비효율적이다. 이 알고리즘은 정확하지만, 매우 오래 걸리고 비효율적인 알고리즘이다.
알고리즘을 평가할 때는 정확성도 중요하지만, 효율성도 중요하다. 효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것이다.
2. 정확하고 효율적인 알고리즘: 중간 페이지부터 찾기
이번에는 더 효율적인 알고리즘을 적용하여 Mike Smith를 찾아보자. 중간부터 찾기 알고리즘이다.
1 전화번호부 가운데를 펼친 후 Mike Smith가 그 페이지에 있는지 찾는다.
2 Smith가 없으면, 목차(색인)를 활용해 Mike Smith가 지금 페이지보다 앞부분에 있는지 뒷부분에 있는지 파악한다.
3 Mike Smith가 있을거로 예상되는 절반에 대해 Mike Smith를 찾을 때까지(=마지막 한페이지) 똑같은 알고리즘을 수행한다.마지막에 남은 한 페이지에는 Mike Smith의 이름이 있거나 없거나 둘 중 하나일거다.
중간부터 찾기 알고리즘은 처음부터 찾기 알고리즘보다 더 효율적이다.
만약 기존 전화번호부가 100페이지고, 100페이지가 또 추가되어 200페이지가 되었다고 가정했을 때 효율성 측면에서 중간부터 찾기 알고리즘이 더 낫다는 걸 알 수 있다.
이 경우 처음부터 찾기 알고리즘은 100번의 페이지를 더 넘겨야 하지만, 절반씩 줄어드는 중간부터 찾기 알고리즘은 단 1번의 절차만 더 수행하면 된다! 단 한 번의 동작으로 200페이지의 반인 100페이지가 사라지기 때문이다.
3. 의사코드(pseudo-code)
위와 같은 알고리즘은 아래와 같은 의사코드라는 방식으로 보다 명료하게 정리할 수 있다.
의사코드는 특정 프로그래밍 언어의 문법에 따라 쓰인 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써놓은 코드를 말한다.
의사코드는 필요한 행동이나 조건을 잘 설정하여 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있게 도와준다.
