반에서 가장 키 큰 사람 찾기 : 선형 알고리즘
반에서 가장 키 큰 사람이 누구인지 알고싶다고 해보자. 사람인 우리는 그냥 딱 보고 알 수 있겠지만, 알고리즘은 어떤 바보같은 컴퓨터라도 이해할 수 있을 정도로 실행단계를 명확하고 상세하게 설명해야한다.
기본적인 방식은 한 명 한 명 차례로 키가 몇인지 묻고, 지금까지 확인한 사람 중에 가장 키 큰 사람이 누군지 계속 체크하는 것이다.
이 방식에서 다른 조건이 추가되면 상황은 복잡해진다. 예를 들면 키가 같은 사람의 경우는 어떻게 할 것인가?
이런 문제를 해결하기 위해서 자료 구조(data structure)가 필요하다.
알고리즘으로 전체 키의 평균을 계산한다고 해보자
set sum to 0 // sum을 0으로 설정한다
for each height on the list // 목록에 있는 각 height 에 더해
add the height to sum // sum 에 height 를 더한다.
set average to sum / N // average를 sum / N으로 설정한다.
하지만 컴퓨터에게 시킬 때는 이 작업보다 더 신중해야한다.
아무런 수도 쓰여있지 않다면 컴퓨터는 무엇을 할지 모르게 된다. 우리는 그럼 알려줘야 한다.
set sum to 0 // sum을 0으로 설정한다
set N to 0 // N을 0으로 설정한다.
repeat these two steps for each height : // 각 height마다 다음 두 단계를 반복한다.
add the next height to sum // sum에 다음 height 를 더한다.
add 1 to N // N에 1을 더한다.
if N is greater than 0 // N이 0보다 크다면
set average to sum / N // average를 sum / N으로 설정한다.
otherwise // 그렇지 않다면
report that no heights were given // 주어진 height가 없다고 말한다.
알고리즘의 중요한 특성 중 하나는 얼마나 효율적으로 작동하느냐다. 알고리즘의 효율성은 알고리즘이 주오진 양의 데이터를 처리하는 데 시간이 얼마나 걸릴 것으로 예상되는가로 측정된다.
계산 시간이 데이터 양에 정비례하거나 선형적으로 비례할 때, 그 알고리즘은 선형 시간(linear-time)또는 단순히 선형(linear)이라고 한다. 이런 선형은 xy그래프를 그려보면 오른쪽 위를 향하는 직선이 될 것이다.
많은 선형 알고리즘은 이런 식의 알고리즘을 띈다.
초기화가 필요하며, 각 항목을 차례로 검사하고, 항목에 대해 간단한 계산을 수행한다. 수를 세거나, 비교하거나, 변환하거나 할 수 있다. 그 이후는 작업을 끝내기 위한 어떤 단계가 필요하다. 예를들면 평균을 계산하거나 가장 큰 값을 출력하는 것이다.
의외로 알고리즘...의 원리는 간단하다.
😵💫
