알고리즘이란 무엇인가

생각 열기 — 숫자 맞히기

짝이 1부터 100까지 중에서 수 하나를 마음속으로 정한다. 우리는 “그 수가 ○○보다 큽니까”라고만 물을 수 있고, 짝은 “예” 또는 “아니오”로만 답한다. 몇 번 물으면 반드시 맞힐 수 있을까?

한 방법은 1부터 차례로 묻는 것이다. “1보다 큽니까”, “2보다 큽니까”…. 정한 수가 98이면 98번쯤 물어야 한다.

다른 방법은 늘 가운데를 묻는 것이다. “50보다 큽니까”로 시작하면 어느 답이 오든 남는 범위가 절반으로 줄어든다.

문제를 푸는 절차 — 알고리즘

알고리즘(algorithm) — 주어진 문제를 해결하기 위한 단계별 절차은 문제를 해결하는 절차다. 1차시에서 프로그래밍은 코드를 타이핑하는 일이 아니라 절차를 찾아내는 일이라고 했다. 그 찾아낸 절차가 알고리즘이고, 4차시 개발 절차의 설계 단계에서 만드는 것이 바로 이것이다.

알고리즘은 프로그래밍 언어와 무관하다. 앞의 숫자 맞히기에서 “가운데를 묻는다”는 절차는 Python으로도 C로도 옮길 수 있고, 종이와 연필로도 실행할 수 있다. 그래서 알고리즘을 먼저 정하면 언어를 바꿔도 다시 생각하지 않는다.

알고리즘이 갖춰야 할 조건

아무 절차나 알고리즘이라 부르지 않는다. 다음 다섯 조건을 지켜야 한다.

알고리즘의 다섯 조건

조건	뜻	어긋난 예
입력	필요한 자료를 밖에서 받는다. 받을 것이 없는 경우도 있다	무엇을 가지고 시작하는지 적혀 있지 않다
출력	결과가 하나 이상 나온다	절차를 다 따라 했는데 무엇을 얻었는지 알 수 없다
명확성	각 단계가 한 가지 뜻으로만 읽힌다	"적당히 데운다" — 몇 도인지 알 수 없다
유한성	유한한 횟수의 단계를 거쳐 반드시 끝난다	"답을 찾을 때까지 되풀이한다" — 못 찾으면 끝나지 않는다
유효성	각 단계를 실제로 실행할 수 있다	"가장 좋은 수를 고른다" — 실행하는 방법이 없다

명확성 — 사람이 알아서 채우게 두지 않는다

라면 봉지에 “물을 적당히 넣고 알맞게 끓인다”고 적혀 있다면 사람은 어떻게든 끓인다. 그러나 이 절차를 그대로 기계에 주면 실행되지 않는다. 몇 밀리리터인지, 몇 도에서 몇 분인지 정해지지 않았기 때문이다.

명확성이 어긋나는 흔한 표현은 정해진 값이 없는 말이다. 적당히, 알맞게, 충분히, 조금, 필요하면. 이런 말이 절차에 남아 있으면 그 부분은 아직 설계되지 않은 것이다.

유한성 — 반드시 끝나야 한다

“답을 찾을 때까지 되풀이한다”는 문장은 답이 없는 경우를 생각하지 않았다. 1부터 100까지 중에서 찾는데 짝이 아무 수도 정하지 않았다면 이 절차는 영원히 돈다.

유한성을 지키려면 끝나는 조건을 절차 안에 적어야 한다. “범위가 하나로 좁혀지면 그 수가 답이다”, “범위가 비면 답이 없다고 알린다” 처럼 모든 경우에 출구가 있어야 한다.

같은 문제, 다른 알고리즘

두 방법 모두 다섯 조건을 지킨다. 둘 다 올바른 알고리즘이다. 그런데 걸리는 횟수가 크게 다르다.

한 번 물을 때마다 범위가 절반이 되므로, 100 → 50 → 25 → 13 → 7 → 4 → 2 → 1 로 일곱 번에 하나가 남는다. 범위를 늘려 보면 차이가 뚜렷해진다.

범위가 커질 때 필요한 최대 질문 횟수

찾을 범위	하나씩 세는 방법	가운데를 묻는 방법
100개	100번	7번
1,000개	1,000번	10번
1,000,000개	1,000,000번	20번

범위가 1만 배로 늘 때 하나씩 세는 방법은 1만 배 더 걸린다. 가운데를 묻는 방법은 13번 늘어날 뿐이다. 자료가 많아질수록 두 알고리즘의 차이는 벌어진다.

효율은 무엇으로 재는가

좋은 알고리즘을 재는 기준을 효율(efficiency) — 같은 문제를 푸는 데 드는 시간과 기억 공간의 정도이라 한다. 효율은 두 가지로 나눠 본다.

• 시간 — 몇 단계를 거쳐야 끝나는가. 앞의 질문 횟수가 이것이다.
• 기억 공간 — 중간 결과를 담아 두려면 얼마나 많은 자리가 필요한가.

이 둘은 흔히 서로 맞바꾼다. 계산한 값을 표로 적어 두면 다시 계산하지 않아 빨라지지만 표를 담을 자리가 더 든다. 반대로 자리를 아끼려면 필요할 때마다 다시 계산해야 하니 느려진다. 어느 쪽을 택할지는 만드는 프로그램의 조건이 정한다.

활동

실습

일상 절차를 알고리즘의 조건에 맞게 다듬기

약 20분

아래 절차는 학교 자판기에서 음료를 뽑는 방법을 적은 것이다. 그대로는 알고리즘이 되지 못한다.

1. 자판기 앞에 선다.
2. 돈을 적당히 넣는다.
3. 마음에 드는 음료의 단추를 누른다.
4. 음료가 나올 때까지 기다린다.
5. 거스름돈을 챙긴다.

1단계. 다섯 조건 중 어긋난 조건을 찾아 각 줄에 표시한다. 어떤 조건이 어떻게 어긋났는지 한 문장으로 적는다.

2단계. 절차를 다시 적는다. 다음을 반드시 넣는다.

• 입력과 출력이 무엇인지 절차 맨 위와 아래에 밝힌다.
• “적당히”, “마음에 드는” 같은 말을 없애고 판단 기준을 정한다.
• 돈이 값보다 적은 경우, 품절인 경우, 거스름돈이 없는 경우의 출구를 넣는다.

3단계. 짝과 종이를 바꿔 적힌 그대로만 따라 해 본다. 적히지 않은 판단은 절대 하지 않는다. 막히는 곳에 표시한다.

4단계. 다듬은 절차가 다섯 조건을 모두 지키는지 표로 점검한다.

조건	지켰는가	근거 (몇째 줄)
입력
출력
명확성
유한성
유효성

개념 확인 문제

보기를 누르면 바로 채점된다. 틀려도 해설을 읽으면 된다.

알고리즘의 조건 중 '유한성'에 대한 설명으로 알맞은 것은?프그01-03

1. 1입력받는 자료의 개수가 정해져 있어야 한다
2. 2유한한 횟수의 단계를 거쳐 반드시 끝나야 한다
3. 3단계의 개수가 열 개를 넘지 않아야 한다
4. 4출력이 하나만 나와야 한다

다음 중 명확성이 어긋난 단계는?프그01-03

1. 1입력받은 점수에 1을 더한다
2. 2점수가 60 이상이면 합격이라고 출력한다
3. 3물을 적당히 넣고 알맞게 끓인다
4. 4값이 0이 될 때까지 1씩 뺀다

1부터 1,000까지 중 하나를 '○○보다 큰가'라는 질문만으로 맞힐 때, 가운데를 묻는 방법으로 필요한 최대 질문 횟수는?프그01-03

1. 110번쯤
2. 2100번쯤
3. 3500번쯤
4. 41,000번

[OX] 효율이 나쁜 절차는 알고리즘이라고 부를 수 없다.프그01-03

1. 1⭕ 그렇다
2. 2❌ 아니다

계산한 결과를 표로 적어 두고 다시 쓰는 방법으로 프로그램을 빠르게 만들었다. 이때 대신 늘어나는 것은?프그01-03

1. 1입력하는 자료의 개수
2. 2필요한 기억 공간
3. 3출력의 개수
4. 4프로그램의 코드 줄 수만 늘고 다른 것은 그대로다

더 알아보기

어원'알고리즘'이라는 말은 사람 이름에서 왔다

9세기 페르시아의 수학자 알콰리즈미(al-Khwārizmī)는 수를 다루는 계산 절차를 체계적으로 정리한 책을 남겼다. 그 책이 유럽에 전해질 때 저자의 이름이 라틴어로 옮겨졌고, 그 말이 굳어 오늘날의 algorithm이 되었다. 컴퓨터가 나오기 1,000년 전에, 절차를 정확하게 적어 두면 누구든 같은 결과를 얻는다는 생각이 이미 있었던 셈이다.

심화가운데를 묻는 방법에는 조건이 하나 붙는다

가운데를 묻는 방법이 늘 쓸 수 있는 것은 아니다. 찾을 대상이 순서대로 정렬돼 있어야 한다. 1부터 100까지의 수는 이미 크기 순이므로 “50보다 큰가”라는 질문이 범위를 반으로 가른다. 그러나 정리되지 않은 명단에서 이름 하나를 찾을 때는 이 방법을 쓸 수 없다. 반을 갈라도 어느 쪽에 있는지 알 수 없기 때문이다. 이 방법을 이진 탐색이라 하고, 하나씩 세는 방법을 순차 탐색이라 한다. 알고리즘을 고를 때는 자료가 어떤 모양인지 함께 봐야 한다.

심화답이 있는지조차 미리 알 수 없는 경우

“이 절차가 끝나는가”를 사람이 판단하는 것은 늘 쉽지 않다. 아주 짧은 절차인데도 끝나는지 아직 아무도 증명하지 못한 예가 수학에 남아 있다. 그래서 유한성은 적어 놓고 눈으로 확인하는 조건이 아니라, 절차를 설계할 때 끝나는 조건을 스스로 넣어 두어야 하는 의무에 가깝다. 반복하는 부분을 적을 때마다 “이 반복은 무엇 때문에 끝나는가”를 한 번씩 되묻는 습관이 도움이 된다.