답이 같아도 일한 양은 다르다
결과만 보면 두 방법을 구별할 수 없습니다.
강당에 의자가 놓여 있고, 몇 개인지 세어 오라는 심부름을 받았다고 해 봅시다. 의자는 한 줄에 12개씩, 모두 20줄로 가지런히 놓여 있습니다. 두 사람이 각각 다른 방법으로 세었습니다.
방법 ㄱ — 하나씩 센다
첫 의자부터 손가락으로 가리키며 「하나, 둘, 셋…」 마지막 의자까지 셉니다.
세는 일 240번
의자 하나마다 한 번씩
방법 ㄴ — 한 줄만 세고 곱한다
한 줄의 의자를 세고, 줄이 몇 줄인지 세고, 두 수를 곱합니다.
세는 일 32번 + 곱하기 1번 = 33번
한 줄 12번, 줄 수 20번, 곱셈 한 번
두 사람이 가져온 답은 똑같이 240개입니다. 답만 보면 두 방법을 구별할 수 없습니다. 구별되는 것은 거기까지 가는 데 든 일의 양입니다.
규모가 커지면 차이도 커진다
강당이 더 큰 곳으로 바뀌어 한 줄에 15개씩 30줄이 되었다고 해 봅시다.
| 강당 크기 | 방법 ㄱ | 방법 ㄴ | 차이 |
|---|---|---|---|
| 12개 × 20줄 (240개) | 240번 | 33번 | 방법 ㄴ이 약 7배 적게 일합니다. |
| 15개 × 30줄 (450개) | 450번 | 46번 | 방법 ㄴ이 약 10배 적게 일합니다. |
의자가 240개에서 450개로 약 두 배가 되는 동안, 방법 ㄱ의 일도 두 배 가까이 늘었습니다. 반면 방법 ㄴ은 33번에서 46번으로 조금 늘었을 뿐입니다. 두 방법의 차이가 벌어진 것입니다.
효율을 비교한다는 것은
같은 문제를 푸는 여러 알고리즘 가운데 어느 것이 더 적은 일로 같은 답에 닿는지를 살펴보는 것입니다.
방법 ㄴ이 언제나 낫지는 않습니다
방법 ㄴ은 의자가 반듯한 네모꼴로 놓여 있을 때만 쓸 수 있습니다. 줄마다 의자 수가 들쭉날쭉하거나 군데군데 빠져 있으면 곱셈이 통하지 않습니다. 효율이 좋은 방법에는 대개 붙는 조건이 있습니다. 그 조건이 맞는지부터 확인하는 것이 먼저입니다.
우리 반 학생 수를 세는 방법을 두 가지 떠올려 보고, 각각 몇 번 일하는지 세어 보세요. 어느 쪽이 적게 일하나요?
무엇으로 측정하는가 — 시간과 공간
초시계로 측정하면 알고리즘이 아니라 그날의 사정을 측정하게 됩니다.
왜 초로 측정하지 않을까
「어느 알고리즘이 빠른가」를 알고 싶으면 초시계를 대면 될 것 같습니다. 그런데 그렇게 측정하면 곤란한 일이 생깁니다.
- 성능이 좋은 컴퓨터에서 측정하면 어떤 알고리즘이든 빨라 보입니다.
- 같은 컴퓨터라도 다른 프로그램이 함께 실행되고 있으면 느려집니다.
- 그래서 오늘 측정한 값과 내일 측정한 값이 달라집니다.
초시계로 측정한 값은 알고리즘의 성질이 아니라 「그날 그 기계의 사정」을 담고 있습니다. 그래서 알고리즘을 측정할 때는 시계 대신 「일을 몇 번 하는가」, 곧 연산 횟수를 셉니다. 연산 횟수는 어느 기계에서 측정해도 같습니다.
시간 복잡도(time complexity)
알고리즘을 끝마치는 데 얼마나 많은 일을 해야 하는지를 측정하는 기준입니다. 연산 횟수로 셉니다.
의자 세기에서 방법 ㄱ은 240번, 방법 ㄴ은 33번. 시간은 이 숫자로 측정합니다.
공간 복잡도(space complexity)
알고리즘이 끝날 때까지 얼마나 많은 기억 장소가 필요한지를 측정하는 기준입니다.
방법 ㄱ은 「지금까지 센 수」 하나만 기억하면 됩니다. 방법 ㄴ은 「한 줄의 수」와 「줄 수」 둘을 기억합니다.
공간이 문제가 될 때
책 열다섯 권을 번호순으로 다시 꽂는다고 해 봅시다. 두 가지 길이 있습니다.
그 책장 안에서만 위치를 바꾼다
책을 서로 맞바꾸어 가며 정리합니다. 빈 책장이 따로 필요 없습니다. 대신 위치를 바꾸는 일이 잦아집니다.
빈 책장을 하나 더 놓고 옮긴다
번호 순서대로 새 책장에 옮겨 꽂습니다. 일하기는 훨씬 수월하지만, 책장 하나를 놓을 공간을 더 써야 합니다.
시간과 공간은 서로 맞바꿀 수 있는 경우가 많습니다. 기억 장소를 더 쓰면 일이 줄고, 기억 장소를 아끼면 일이 느는 식입니다. 둘 다 아끼는 방법이 늘 있는 것은 아닙니다. 그래서 「효율적인 알고리즘」이라는 말에는 언제나 「무엇을 기준으로」가 따라붙습니다.
같은 프로그램을 학교 컴퓨터와 내 휴대 전화에서 실행했더니 걸린 시간이 달랐습니다. 이때 알고리즘이 달라진 것일까요? 아니라면 무엇이 달라진 것일까요?
데이터가 많아질 때 비로소 드러난다
열 개일 때는 눈에 띄지 않던 차이가 만 개에서는 크게 벌어집니다.
일하는 방식이 다른 세 가지 알고리즘을 놓고, 다룰 데이터가 늘어날 때 일하는 횟수가 어떻게 불어나는지 세어 보겠습니다. 셋은 각각 이런 방식입니다.
- 하나씩 다 보기 — 처음부터 끝까지 하나도 빠짐없이 한 번씩 본다.
- 절반씩 버리기 — 한 번 볼 때마다 남은 것의 절반을 지운다.
- 모든 짝을 한 번씩 보기 — 둘씩 짝지을 수 있는 모든 경우를 한 번씩 본다.
| 데이터 개수 | 하나씩 다 보기 | 절반씩 버리기 | 모든 짝 보기 |
|---|---|---|---|
| 10개 | 10번 | 4번 | 45번 |
| 100개 | 100번 | 7번 | 4,950번 |
| 1,000개 | 1,000번 | 10번 | 499,500번 |
| 10,000개 | 10,000번 | 14번 | 49,995,000번 |
데이터가 10개에서 10,000개로 1,000배가 되는 동안 각 방식이 어떻게 되었는지 보세요. 하나씩 다 보기도 꼭 1,000배가 되었습니다. 절반씩 버리기는 4번에서 14번으로, 겨우 서너 배 늘었을 뿐입니다. 모든 짝 보기는 45번에서 약 5,000만 번으로 백만 배 넘게 불어났습니다.
다룰 것이 적을 때는 차이가 보이지 않습니다
데이터가 10개일 때를 보세요. 4번과 10번, 그리고 45번입니다. 사람이 손으로 해도 어느 쪽이든 금방 끝납니다. 효율의 차이는 다룰 것이 많아져야 비로소 드러납니다. 그래서 작은 예로 시험해 보고 「충분히 빠르다」고 판단하는 것은 위험합니다. 실제로 쓸 만큼의 데이터를 넣어 봐야 알 수 있습니다.
불어나는 「모양」에 이름을 붙인다
세 방식의 일하는 횟수를 센 표에서 우리가 실제로 본 것은 정확한 숫자가 아니라 불어나는 모양입니다. 「데이터를 두 배로 늘리면 일도 두 배가 되는가, 한 번만 더 하면 되는가, 네 배가 되는가」 하는 것입니다. 이 모양에 이름을 붙여 적는 방법을 빅오 표기법이라고 하고, 알파벳 O를 씁니다.
| 불어나는 모양 | 이렇게 적는다 | 데이터를 두 배로 늘리면 |
|---|---|---|
| 데이터가 늘어도 그대로 | O(1) | 일이 늘지 않습니다. |
| 절반씩 버리기 | O(log n) | 일이 한 번 정도 늘어납니다. |
| 하나씩 다 보기 | O(n) | 일도 두 배가 됩니다. |
| 모든 짝 보기 | O(n²) | 일이 네 배 가까이 됩니다. |
n은 다룰 데이터의 개수입니다. 빅오 표기는 자잘한 숫자를 일부러 버립니다. 「정확히 몇 번인가」가 아니라 「커질 때 어떤 모양으로 불어나는가」만 남기려는 것입니다. 여기서는 이런 표기가 있다는 것과 네 가지 모양을 알아보는 것까지만 합니다.
어떤 알고리즘에 데이터를 두 배로 넣었더니 일하는 횟수가 네 배가 되었습니다. 빅오 표기의 네 가지 모양 중 어느 것에 가장 가까울까요?
고른다는 것은 무엇을 내려놓을지 정하는 일
모든 면에서 가장 좋은 알고리즘은 흔치 않습니다.
여기까지 오면 「그러면 가장 빠른 것을 고르면 되겠다」고 생각하기 쉽습니다. 그런데 실제로 알고리즘을 고를 때는 빠르기 말고도 검토해야 할 것이 있습니다.
가장 먼저 볼 것은 정확성입니다
틀린 답을 빨리 내는 알고리즘은 쓸모가 없습니다. 효율은 답이 맞는다는 것이 확인된 다음에 검토하는 것입니다. 빠르게 만들려다 어떤 경우에 답이 어긋나게 되었다면, 그것은 개선이 아니라 고장입니다.
상황이 기준을 정한다
같은 알고리즘이라도 어디에 쓰느냐에 따라 좋은 선택이 되기도 하고 나쁜 선택이 되기도 합니다.
| 이런 상황이면 | 무엇을 지키고 | 무엇을 내려놓게 되는가 |
|---|---|---|
| 기억 장소가 빠듯한 작은 기기에서 실행한다 | 공간을 아낀다 | 기억 장소를 덜 쓰는 대신 일이 늘어 느려질 수 있습니다. |
| 사람이 기다리는 화면에서 바로 답이 나와야 한다 | 속도를 지킨다 | 미리 계산해 저장해 두는 만큼 기억 장소를 더 씁니다. |
| 데이터가 몇 개 되지 않는다 | 단순함을 지킨다 | 이론상 더 빠른 방법을 굳이 쓰지 않습니다. 차이가 거의 없기 때문입니다. |
| 여럿이 오래 고쳐 가며 쓸 프로그램이다 | 읽기 쉬움을 지킨다 | 가장 빠른 방법 대신 알아보기 쉬운 방법을 고르기도 합니다. |
「가장 좋은 알고리즘」이라는 말은 반쪽짜리입니다
표의 어느 줄도 「틀린 선택」이 아닙니다. 각 줄은 지키기로 한 것이 다를 뿐입니다. 그래서 「가장 좋은 알고리즘」이 아니라 「이 상황에서 가장 알맞은 알고리즘」이라고 말해야 정확합니다. 어떤 알고리즘을 고르겠다고 말할 때는 무엇을 기준으로 삼았는지를 함께 말해야 합니다.
그래서 알고리즘을 짠 다음에는
알고리즘을 만들었다고 일이 끝나는 것이 아닙니다. 다음 세 가지를 확인합니다.
답이 맞는가
평범한 경우뿐 아니라 데이터가 하나도 없을 때, 모두 같은 값일 때처럼 드문 경우에도 답이 맞는지 봅니다.
얼마나 일하는가
연산 횟수를 세어 보고, 실제로 쓸 만큼의 데이터를 넣었을 때도 견딜 만한지 확인합니다.
남이 읽을 수 있는가
나중에 고쳐야 할 사람이 무슨 일을 하는 알고리즘인지 알아볼 수 있는지 봅니다.
친구가 「내가 만든 알고리즘이 제일 좋다」고 말합니다. 이 말이 성립하려면 친구가 무엇을 함께 밝혀야 할까요? 두 가지 이상 들어 보세요.
핵심 정리
알고리즘의 효율
같은 답, 다른 품
- 같은 답에 더 적은 일로 닿는가를 살펴보는 것
- 결과만 보면 두 알고리즘을 구별할 수 없다
- 효율이 좋은 방법에는 대개 조건이 붙는다
시간 복잡도
time complexity
- 끝마치는 데 얼마나 많은 일이 필요한가
- 초가 아니라 연산 횟수로 센다 — 시계는 기계 사정을 측정한다
- 불어나는 모양은 O(1) · O(log n) · O(n) · O(n²)처럼 적는다
공간 복잡도
space complexity
- 끝날 때까지 얼마나 많은 기억 장소가 필요한가
- 시간과 맞바꿀 수 있는 경우가 많다 — 기억 장소를 더 쓰면 일이 줄기도 한다
- 둘 다 아끼는 방법이 늘 있는 것은 아니다
알고리즘 고르기
무엇을 기준으로
- 정확성이 먼저다 — 틀린 답을 빨리 내는 것은 쓸모없다
- 차이는 데이터가 많아져야 드러난다
- 「가장 좋은」이 아니라 「이 상황에서 가장 알맞은」
확인 퀴즈
배운 내용을 확인해 봅시다.
알고리즘의 빠르기를 초시계로 측정하지 않고 연산 횟수로 세는 까닭은?
데이터가 10개에서 10,000개로 늘었을 때 일하는 횟수가 4번에서 14번이 된 알고리즘의 방식은?
알고리즘을 고르는 일에 대한 설명으로 옳지 않은 것은?