[CS50] 알고리즘

우리가 컴퓨터에 입력한 자료를 출력형태로 만들기 위해서는 컴퓨터의 처리과정, 즉 명령어들의 순서상 처리가 필요한데 이를 알고리즘이라고 한다.

컴퓨터의 알고리즘도 입력된 자료가 출력 형태로 나가기 위해 순서에 따라 실행해야 하는 명령어들을 보다 효율적으로 나열하게 된다면 시간과 공간을 단축할 수 있다.

 

알고리즘

컴퓨팅은 입력을 받아 그 입력을 처리한 후 출력하는 과정이다. 알고리즘은 입력에서 받은 자료를 출력형태로 만드는 처리 과정을 뜻한다. 즉, 알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열을 말한다. 이러한 일련의 순서적 규칙들의 나열 방법에 따라 알고리즘의 종류가 달라진다. 같은 출력값이라도 알고리즘적 순서 나열에 따라 출력값에 도달하는 시간은 서로 다를 수 있다.

 

 

정확한 알고리즘 (정확성)

알고리즘은 입력을 출력으로 바꾸기 위해 컴퓨터가 따르는 일련의 절차이다. 알고리즘은 우리의 일상생활 언어로도 표현할 수 있습니다. 절차를 순서대로나열한 목록처럼 말이다. 

 

이를 수도코드 (의사코드) pseudocode 라고 부는데

알고리즘을 프로그래밍 언어를 사용하지 않고 표현하는 방법을 말한다. 예를 들어 아래의 나열된 코드 형식의 명령들은 전화번호부에서 마이크 스미스를 찾는 수도코드라고 할 수 있다. 수도코드에 형식이 있는 것은 아니지만, 수도코드를 작성할 때 명심해야하는 부분은 일어날 수 있는 모든 가능성을 예상해야한다는 것이다.

 

예를 들어, 전화번호부에서 Mike Smith를 찾는 일을 한다고 해보자. 왼쪽 <코드1>의 알고리즘을 살펴보면, 전화번호부를 집어 들고 첫 페이지를 펼친 후 Mike Smith가 그 페이지에 있는지 찾고 없으면 그 다음 페이지에서 찾는다. Mike Smith 를 찾을 때까지 혹은 전화번호부가 끝날 때까지 이것을 반복한다.

이 알고리즘은 정확하다. 만약 Mike Smith 가전화번호부에 있다면 이 알고리즘을 사용한 사람은 Mike Smith 를 찾아내는 데 성공할 것이다.  

 

<코드1>

알고리즘의 평가할 때는 정확성도 중요하지만, 효율성도 중요하다. 효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 척도이다. 한 번에 한 페이지씩 보는 알고리즘은 정확하지만, 효율적이지는 않다. 한 번에 두 페이지를 넘기게끔 하여 알고리즘을 개선할 수도 있다. 하지만 이 알고리즘을 그대로 사용한다면 Mike Smith가 있는 페이지가 그냥 넘어갈 수도 있으니 주의해야 할 것이다. 이럴 때는 이전 페이지를 확인해야 하지만 이 알고리즘마저도 이 문제를 해결하기에 가장 효율적이지는 않다.

 

효율적인 알고리즘 (효율성)

더 직관적이고 효율적인 알고리즘이 뭐가 있을지 생각해보자.  이번에는 다른 알고리즘 <코드2>를 적용하여 Mike Smith를 찾아볼 것이다. 먼저, 전화번호부 가운데를 편다. 만약 Mike Smith가 그 페이지에 있다면 우리 알고리즘은 끝난다. 없다면, 전화번호부가 이름순으로 정렬되어 있으므로 우리는 Mike Smith가 지금 페이지보다 앞부분에 있는지 뒷부분에 있다는 것을 알 수 있다. 그러므로 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 똑같은 알고리즘을 한 페이지가 남을 때까지 계속 수행한다. 마지막에 남은 한 페이지에는 Mike Smith의 이름이 있거나 없거나 둘 중 하나일 것이다.

 

<코드2>

코드2의 알고리즘은 기존 알고리즘보다 더 효율적이다. 만약 500페이지가 추가되었다고 가정해 보자. 첫 번째 알고리즘을 사용한다면, 추가된 500페이지에 대해 절차가 500번 더 수행될 것이다. 하지만 두 번째 알고리즘을 사용한다면, 단 1번만 추가로 수행하면 된다.