알고리즘이란?

알고리즘과 프로그램의 차이

'알고리즘(Algorithm)'이란, 계산이나 작업을 하기 위한 순서를 의미한다.

 

요리의 레시피와 같다고 생각하면 된다.어떤 요리를 만들기 위한 순서를 레시피라고 하면,

특정 문제를 컴퓨터로 해결하기 위한 순서가 알고리즘.

 

예를 들어

'아무렇게나 나열돼있는 숫자를 작은 순서부터 차례로 정렬하기'

'출발점부터 목적지까지의 경로 중 최단 경로 찾기' 등

 

알고리즘은 프로그램과 비슷하다고 생각할 수도 있다.

하지만 프로그램은 컴퓨터상에서 실행할 수 있도록 컴퓨터가 이해할 수 있는 언어로 작성하는 것에 반해,

알고리즘은 프로그램을 작성하기 이전 단계에서 사람이 이해할 수 있도록 작성하는 것.

 

같은 알고리즘이라도 프로그래밍 언어가 다르면 다른 프로그램이 되며,

같은 프로그래밍 언어를 사용한다고 해도 프로그램을 작성하는 사람에 따라 다른 프로그램이 된다.

 

 

 

 

계산 시간을 측정하는 방법

입력 변화에 따른 계산 시간 변화는 어떻게 구할까.

 

계산 시간에는 '스탭 수'를 활용한다.

'1스탭'은 계산의 기본 단위로, '계산을 종료하기까지 기본 단위를 몇 회 실행했는가'로 계산 시간을 측정한다.

 

 

 

계산 시간을 표현하는 방법

O는 '중요한 항목 이외는 무시한다'라는 의미를 가지는 기호.

O는 '오더(order)' 또는 '빅오(Big O)'라고 읽는다.

 

O(n²)는 '계산 시간이 최악의 경우 n²의 배수가 된다'는 것을 의미하지만, 정확한 정의는 전문 서적을 참고하자.

중요한 것은 이 표기에 따라 알고리즘의 계산 시간을 직관적으로 이해할 수 있다는 것.

 

예를 들어, 선택 정렬의 계산 시간이 O(n²)이며 퀵 정렬(quick sort)의 계산 시간이 O(n log n)라는 정보가 주어진 경우,

퀵 정렬의 계산 시간이 빠르다는 것을 바로 알 수 있다.

또한, 입력의 크기 n의 변화에 따라 계산 시간이 어느 정도 달라지는지도 한눈에 파악할 수 있다.

 

---

참고 서적

'알고리즘 도감:그림으로 배우는 알고리즘26 (이시다 모리테루, 미야자키 쇼이치 지음 / 김완섭 옮김)'