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

알고리즘?
계산이나 작업을 하기 위한 순서

요리의 레시피와 같다고 생각하면 된다.
특정 문제를 컴퓨터로 해결하기 위한 순서가 알고리즘이다.

But, 레시피와 알고리즘의 결정적인 차이는 알고리즘은 모든 순서가 수학적으로 기술되기 때문에 '대충'이 허용되지 않고 엄격하다.

알고리즘은 프로그램과 비슷하다고 생각할 수 있지만,
프로그램은 컴퓨터상에서 실행할수 있도록 컴퓨터가 이해할 수 있는 언어로 작성하는 것에 반해,
알고리즘은 프로그램을 작성하기 이전 단계에서 사람이 이해할 수 있도록 작성하는 것이다.
단, 어디까지가 알고리즘이고 어디부터가 프로그램인가를 분명하게 구분 짓는 것은 어렵다.

알고리즘의 설계

컴퓨터는 몇 개의 기본 명령을 가지고 있어서 이것을 빠르게 실행하는 것이 특기지만 복잡한 명령을 실행하는 건 어렵다.

컴퓨터는 이 기본 명령들을 조합해서 동작하며, 복잡한 작업도 명령의 조합으로 대처한다.
'n개의 숫자를 정렬한다'라는 처리도 컴퓨터에게는 복잡한 작업에 해당된다.
이 순서를 컴퓨터도 실행할 수 있는 기본 명령의 조합으로 작성하는 것이 알고리즘 설계에 해당된다.

알고리즘 선택 방법

같은 문제를 푸는 알고리즘이 여러 개 있을 때는 어떤 것을 사용하면 좋을까?
알고리즘을 평가하는 기준에는 여러 가지가 있다.
일반적으로 가장 중요시되는 것은 계산 시간이다.
즉, 주어진 입력 값으로 답을 내기까지 걸리는 시간이다.

완전 탐색에 의한 정렬

비효율적인 알고리즘을 사용하면 어떤 일이 벌어지는지 체감하기 위해 정렬에 다음과 같은 '완전 탐색 알고리즘'을 적용한다면,

1. n개의 숫자가 나열된 수열을 하나 만든다.(단, 지금까지 사용하지 않은 나열 순서)
2. 1에서 만든 수열이 왼쪽부터 작은 순서대로 나열돼 있으면 출력한다. 작은 순서대로 나열돼 있지않다면 1로 돌아가 수열을 다시 만든다.

나열된 것을 모두 확인하므로 어떤 입력 값이 주어지더라도 반드시 맞는 답을 출력한다.

n개의 숫자가 나열돼 있다면 n!(n factorial)만큼의 경우의 수를 생각할 수 있다.

n = 50이면,
50! = 50 49 48 ... 3 2 1

10이하의 수를 버리고 10$^4$$^0$ 이라고 했을때,
고성능 컴퓨터를 사용해서 1초에 1조(=10$^1$$^2$)개의 수열을 확인할 수 있다면, 10$^4$$^0$ ÷ 10$^1$$^2$ = 10$^2$$^8$초가 된다.
1년은 31,536,000초로 10$^8$초 미만이다. 따라서 10$^2$$^0$년이 된다.

빅뱅이 시작된 우주의 연령이 137억년이라고 알려져 있지만 10$^1$$^1$년보다 짧은 시간인데, 완전 탐색 알고리즘을 사용해서 단 50개의 숫자를 정렬하고자 한다면 우주의 나이가 10$^9$회 반복되는 것을 기다려도 답이 출력되지 않는다.

선택정렬을 사용하는 경우

선택정렬?
수열 중에서 최솟값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 정렬 방법

1. 수열을 선형 탐색해서 최솟값을 찾는다.
2. 최솟값을 왼쪽 끝에 있는 수와 교체한 뒤 정렬이 끝난 것으로 간주한다.
3. 모든 값이 정렬될 때까지 (1)~(2) 작업을 반복한다.

1라운드에서 가장 작은 숫자를 찾으려면 수열을 왼쪽부터 오른쪽까지 한 번 보면 되므로 n개의 숫자를 확인하기만 하면 된다.
2라운드에서는 n-1개의 수열 중에서 가장 작은 값을 찾으므로 n-1개의 숫자를 확인한다.
이렇게 n라운드까지 반복하면 전체적으로는 다음의 횟수로 숫자를 체크하게 된다.

(n-1)+(n-2)+ … + 2 + 1 = n(n-1)/2 = n$^2$

n=50인 경우는 n$^2$=2500이다.
1초에 1조(=10$^1$$^2$)개의 숫자를 확인할 수 있다면,
2500 ÷ 10$^1$$^2$ = 0.0000000025초에 답이 출력된다.
완전 탐색 알고리즘과 비교하면 매우 빠른 속도이다.

계산시간 측정

알고리즘 실행 시간은 같은 알고리즘에서도 입력의 크기에 따라 알고리즘 계산시간이 얼만큼 달라지는지도 고려해야 한다.

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

O는 '중요한 항목 이외는 무시한다'라는 의미를 가지는 기호이다.
O는 '오더(order)' 또는 '빅오(big O)'라고 읽는다.
O(n$^2$)는 '계산 시간이 최악의 경우 n$^2$의 배수가 된다'는 것을 의미하지만, 정확한 정의는 전문서적을 참고..
중요한 것은 이 표기에 따라 알고리즘의 계산 시간을 직관적으로 이해할 수 있다는 것이다.

---

Reference

• 『알고리즘 도감』, 이시다 모리테루, 미야자키 쇼이치 - 제이펍