선형 알고리즘

반에서 가장 키 큰 사람이 누구인지 알고 싶다고 해보자. 그냥 둘러봐도 어림짐작할 수 있겠지만, 알고리즘은 바보 같은 컴퓨터도 이해할 수 있을 정도로 실행 단계를 명확하고 상세하게 설명해야 한다. 기본적인 접근 방식은 한 명 한 명 차례로 키가 몇인지 묻고, 지금까지 확인한 사람 중에 가장 키 큰 사람이 누군지 계속 체크하는 것이다. 사람들에게 돌아가며 다음과 같이 물어볼 수 있다. '철수야, 키가 몇이니?' 만일 철수가 처음으로 키를 물어본 것이라면 지금까지는 철수가 가장 키 큰 사람이다. '영희야 키가 몇이니?' 철수 다음으로 영희에게 키를 물어봤는데 영희가 더 크다면 이제 영희가 가장 키 큰 사람이고 ,그렇지 않다면 철수가 순위를 유지한다. 어떻든 세 번째 사람에게도 이어서 질문하고, 이런 식으로 절차의 끝까지 도달하여 모든 학생에게 물어보면 가장 키 큰 사람과 그의 키를 알 수 있다. 이 방법으로 알아낼 수 있는 것으로는 재산이 가장 많은 사람, 한글순으로 이름이 가장 앞에 오는 사람, 또는 생일이 가장 느린 사람 등이 있다

 다른 조건이 추가되면 사황이 복잡해진다. 만약 중복되는 값이 있을 땐 어떻게 다뤄야 할까? 예를 들어 두 명 이상의 학생이 키가 같다면? 먼저 물어본 사람을 기록해야 할지, 나중에 물어본 사람을 기록해야 할지, 아니면 임의로 선택해야 할지, 아니면 모두 기록해야 할지 정해야 한다. 가장 키 큰 사람을 찾는 게 아니라, 키가 같은 사람들의 무리 중에서 사람 수가 가장 많은 무리를 찾는 일은 훨씬 더 어려운 문제라는 점에 주목하자. 왜냐하면 키가 같은 사람 모두의 이름을 기억해야 하기 때문이다. 이 경우 입력 끝에 가서야 최종 명단에 누가 있는지 알게 될 것이다. 이런 문제를 해결하려면 자료 구조가 필요하다 자료 구조는 계산 과정에서 필요한 정보를 표현하는 방법이다. 자료 구조는 많은 알고리즘에서 중요하게 고려해야 할 사항이지만 여기서 자세히 설명하지는 않겠다.

 전체 키의 평균을 계산하고 싶다면 어떻게 해야 할까? 각 사람에게 키를 물어보고 입수한 키의 값을 합산하고(아마도 일련의 수를 합산하는 모형 컴퓨터 프로그램을 사용하여), 마지막에 총 합계를 사람 수로 나눠서 평균을 구할 수 있을 것이다. 종이에 N명의 키 목록이 쓰여 있다면 알고리즘으로 해결할 수 있을 것이다

 

합계를 0으로 설정하고

목록에 있는 각 키를 합계에 더해주고

합계를 N으로 나눠 평균을 구해준다

 

하지만 컴퓨터에 이 작업을 요청하려면 더 신중해야 한다. 예를 들어 종이에 아무런 수도 쓰여 있지 않다면 어떻게 될까?

만일 사람이 이 작업을 한다면 할 일이 없다는 것을 금방 알아차릴 수 있기 때문에 문제가 되지 않는다. 반면, 컴퓨터에게는 아무것도 쓰여 있지 않을 가능성에 대해 검사해야 한다고, 또 실제로 그런 경우가 발생했을 때 어떻게 해야 하는지도 알려 줘야 한다. 검사가 수행되지 않으면 결과적으로 합계를 으로 나누려고 시도하게 될 텐데, 이는 정의되지 않은 연산이다. 알고리즘과 컴퓨터는 모든 가능한 상황을 처리해야 한다. 만약 여러분이 한 번이라도 '0원'으로 발행된 수표나 0원을 납부하라는 고지서를 받아 보았다면 모든 경우를 제대로 검사하지 못한 예를 만난 것이다.

 보통 그렇듯이, 데이터 항목이 몇 개인지 미리 알 수 없다면 어떻게 해야 할까? 이 경우에는 합계를 계산하면서 항목의 개수도 세어야 한다

 

합계를 0으로 설정한다

N을 0으로 설정한다

각 키마다 합계에 키를 더하고, N에 1을 더한다

N이 0보다 크다면, 평균을 합계 / N 으로 설정한다

                               그렇지 않다면 키가 없다고 알린다.

 

위 알고리즘은 처리하기 곤란한 경우를 명시적으로 검사함으로써 잠재적으로 발생할 수 있는 '0으로 나누기' 문제를 해결하는 한 가지 방법을 보여준다.

 알고리즘에서 중요한 특성 하나는 얼마나 효율적으로 작동하느냐다. 알고리즘의 효율성은 '알고리즘이 빠른가, 느리가?', '주어진 양의 데이터를 처리하는 데 시간이 얼마나 걸릴 것으로 예상되는가?'와 같은 질문에 대한 답이다. 앞의 예제에서 수행할 단계의 수, 또는 컴퓨터가 이 작업을 하는데 걸리는 시간은 처리해야 하는 데이터의 양에 정비례한다. 만약 방 안에 있는 사람의 수가 두 배이면 가장 키 큰 사람을 찾거나 평균 키를 계산하는 데 두 배의 시간이 걸릴 것이고, 사람의 수가 10배라면 처리하는 데 10배의 시간일 걸릴 것이다. 계산 시간이 데이터의 양에 정비례하거나 선형적으로 비례할 때, 그 알고리즘은 선형 시간 또는 단순히 선형이라고 한다. 데이터 항목의 수를 x축으로 놓고 실행 시간을 y축으로 해서 그래프를 그려 보면 오른쪽 위를 향하는 직선이 될 것이다. 일상생활에서 접하는 많은 알고리즘은 선형이다. 왜냐하면 어떤 데이터에 대해 동일한 기본 연산을 수행해야 하는데, 데이터 수가 많아지면 곧 그에 정비례하게 많은 일이 필요하기 때문이다.

 많은 선형 알고리즘이 동일한 기본 형태를 갖는다. 먼저 초기화가 필요하다. 예를 들면 누적 합계를 0으로 설정하거나, 가장 작은 키를 어떤 작은 값으로 설정하는 것이다. 다음으로 각 항목을 차례로 검사하고, 항목에 대해 간단한 계산을 수행한다. 수를 세거나, 이전 값과 비교하거나, 간단한 방식으로 변환하거나, 아마 출력할 것이다. 마지막에는 작업을 끝내기 위한 어떤 단계가 필요하다. 예를 들면 평균을 계산하거나 합계나 가장 큰 키를 출력하는 일이다. 만약 각 항목에 대한 연산에 거의 같은 시간이 걸린다면 소요되는 전체 시간은 항목의 수에 비례한다.