알고리즘

문제를 푸는 순서에 붙인 이름

늘 해 오던 일에 이름을 붙여 봅니다.

간식을 사람들에게 똑같이 나누는 프로그램을 만든다면 푸는 순서를 여섯 줄로 적을 수 있습니다. 간식 개수와 사람 수를 입력받고, 사람 수가 1보다 작은지 보고, 몫과 나머지를 구하고, 결과를 보여 주는 순서입니다. 그것이 알고리즘입니다.

알고리즘(algorithm)

어떤 문제를 푸는 방법을 단계로 나누어 순서대로 적어 놓은 것입니다. 누가 그 순서를 따라가든 같은 결과에 이르러야 하고, 언젠가는 끝나야 합니다.

프로그램에만 있는 것이 아닙니다. 라면 봉지 뒤의 조리법, 종이접기 설명서, 길 안내가 모두 같은 모양입니다. 단계로 나뉘어 있고, 순서가 정해져 있고, 따라 하면 결과에 이릅니다. 다만 사람이 읽을 조리법은 빈틈이 있어도 사람이 메워 주지만, 컴퓨터에게 줄 알고리즘은 빈틈이 있으면 그대로 어긋납니다.

알고리즘과 프로그램은 어떻게 다른가요

알고리즘은 푸는 방법 그 자체이고, 프로그램은 그 방법을 특정 언어로 적어 놓은 것입니다. 그래서 알고리즘 하나로 여러 개의 프로그램을 만들 수 있습니다. 같은 여섯 줄을 C로 적으면 C 프로그램이 되고 Python으로 적으면 Python 프로그램이 됩니다. 알고리즘은 언어를 고르기 전에 이미 정해집니다.

스스로 확인

「라면 조리법은 알고리즘이다」라고 할 수 있을까요? 알고리즘 정의에 든 세 요소(단계 · 같은 결과 · 끝남)에 하나씩 대 보고 답해 보세요.

순서를 적었다고 다 알고리즘일까

빠지면 알고리즘이라고 부를 수 없는 조건이 다섯 있습니다.

1. 입력 — 받는 것은 없어도 된다

밖에서 받아들이는 값이 0개 이상이면 됩니다. 그래서 아무것도 안 받고 「1부터 100까지 더하기」만 하는 것도 알고리즘입니다.

2. 출력 — 내놓는 것은 반드시 있어야 한다

결과가 하나 이상 나와야 합니다. 아무 결과도 내놓지 않는다면 무엇을 풀었는지 알 길이 없습니다. 입력과 달리 0개는 안 됩니다.

3. 명확성 — 한 가지로만 읽혀야 한다

각 단계가 여러 뜻으로 읽히면 안 됩니다. 「적당히 익힌다」는 사람마다 다르게 하지만 「3분간 끓인다」는 누가 해도 같습니다. 「성적이 높은 학생을 찾아 줘」는 몇 명인지, 기준이 무엇인지가 정해지지 않아 이 조건에 걸립니다.

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

단계를 따라가다 보면 언젠가 끝에 닿아야 합니다. 영원히 도는 것은 답을 내놓지 못하므로 알고리즘이 아닙니다. 「1을 계속 더한다」처럼 멈추는 조건을 안 적으면 여기에 걸립니다.

5. 수행 가능성 — 실제로 할 수 있어야 한다

각 단계가 정말 해낼 수 있는 일이어야 합니다. 「가장 좋은 답을 떠올린다」는 뜻은 분명해 보여도 실제로 실행할 방법이 없습니다.

유한성은 「빨리 끝난다」는 뜻이 아닙니다

끝나기만 하면 조건은 지킨 것입니다. 백 년 걸려 끝나는 것도 유한성은 만족합니다. 쓸 만한가는 다른 이야기이고, 그 이야기는 「같은 답, 다른 방법」 절에서 합니다. 조건을 지켰다는 것과 좋다는 것은 다릅니다.

스스로 확인

「반 학생들의 키를 입력받아 모두 더하고 학생 수로 나눈다. 구한 값은 어디에도 보여 주거나 저장하지 않는다」 — 이것은 다섯 조건 중 어느 것을 어기고 있을까요?

같은 알고리즘, 세 가지 적는 법

머릿속의 순서를 남에게 보이려면 어떻게 적어야 할까요?

알고리즘은 머릿속에만 있으면 남과 나눌 수 없습니다. 적어야 합니다. 적는 방법은 크게 셋인데, 어느 것이 옳은 것이 아니라 쓰임이 다릅니다. 자연어 · 의사코드 · 순서도로 적은 것은 모두 같은 간식 나누기 알고리즘입니다.

1. 자연어 — 우리 말로 적는다

간식 개수와 사람 수를 입력받는다.
사람 수가 1보다 작으면 나눌 수 없다고 알리고 끝낸다.
간식 개수를 사람 수로 나눈 몫과 나머지를 구한다.
한 사람당 몫만큼, 나머지만큼 남는다고 알린다.

누구나 바로 읽을 수 있습니다. 대신 문장이 길어지면 흐름이 흐려지고, 쓰는 사람에 따라 애매한 말이 섞여 들어가기 쉽습니다. 설계를 처음 잡을 때 쓰기 좋습니다.

2. 의사코드 — 코드처럼 생기게 적는다

입력: 간식개수, 사람수

만약 사람수 < 1 이면
    "나눌 수 없습니다" 출력
    끝낸다

한사람당 ← 간식개수 나눈몫 사람수
남는것  ← 간식개수 나머지 사람수

출력: 한사람당, 남는것

의사코드(pseudocode)는 어느 프로그래밍 언어도 아니면서 코드와 비슷한 모양으로 적은 것입니다. 「의사(擬似)」는 「비슷하다」는 뜻입니다. 문법이 정해져 있지 않아 사람마다 조금씩 다르게 적습니다. 자연어보다 짧고 흐름이 또렷해서 코드로 옮기기 직전에 쓰기 좋습니다.

3. 순서도 — 그림으로 그린다

순서도(flowchart)는 정해진 도형과 화살표로 흐름을 그린 것입니다. 나뉘고 되돌아오는 흐름이 눈에 바로 들어와서 「이 경우에는 어디로 가지?」를 확인하기 좋습니다. 대신 단계가 많아지면 종이가 모자랍니다. 「순서도로 그려 본다」 절에서 직접 그려 봅니다.

방법	좋은 점	언제 쓰나
자연어	누구나 바로 읽는다	처음 순서를 잡을 때
의사코드	짧고 흐름이 또렷하다	코드로 옮기기 직전
순서도	나뉘는 흐름이 한눈에 보인다	조건과 반복을 확인할 때

프로그래밍 언어로 적으면 안 되나요

적어도 됩니다. 다만 그렇게 적는 순간 그것은 이미 구현 단계입니다. 자연어 · 의사코드 · 순서도를 따로 두는 이유는 언어를 고르기 전에, 문법을 신경 쓰지 않고 순서만 붙들고 생각하기 위해서입니다. 세 방법 가운데 어느 것으로 적었든 알고리즘 하나가 C 프로그램도 되고 Python 프로그램도 됩니다.

스스로 확인

간식 나누기의 자연어 네 줄과 의사코드를 나란히 놓고 보세요. 의사코드에는 있는데 자연어에는 안 보이는 것이 하나 있습니다. 무엇일까요? 힌트 — 들여쓰기가 무엇을 나타내고 있나요?

순서도로 그려 본다

도형 넷이면 웬만한 흐름은 다 그릴 수 있습니다.

순서도는 도형마다 뜻이 정해져 있습니다. 그래서 그린 사람이 설명하지 않아도 다른 사람이 읽을 수 있습니다. 아무 모양이나 쓰면 그 약속이 깨집니다.

도형	뜻	간식 나누기에서는
타원	시작과 끝	맨 위와 맨 아래
평행사변형	입력과 출력	개수를 입력받는 곳, 결과를 알리는 곳
직사각형	처리 — 계산하거나 값을 정한다	몫과 나머지를 구하는 곳
마름모	판단 — 조건을 보고 길이 나뉜다	사람 수가 1보다 작은지 보는 곳
화살표	다음에 갈 곳	도형 사이를 잇는 선

간식 나누기 순서도

「같은 알고리즘, 세 가지 적는 법」 절의 자연어 네 줄과 같은 알고리즘입니다. 다만 순서도에서는 「끝낸다」가 어디로 가는지가 눈에 보입니다. 두 갈래로 나뉜 길이 결국 같은 「끝」으로 모입니다. 글로 적었을 때는 이 모임이 잘 보이지 않았습니다.

나뉜 길은 끝까지 이어져야 한다

마름모에서 나뉜 두 길은 어딘가에서 다시 모이거나 각자 끝에 닿아야 합니다. 화살표가 허공에서 끊기면 그 경우에 무슨 일이 일어나는지 아무도 모릅니다.

되돌아가는 화살표가 반복이다

위로 되돌아가는 화살표를 그리면 그 구간이 반복됩니다. 이때 빠져나가는 마름모를 반드시 함께 두어야 합니다. 없으면 영원히 돌게 되어 유한성을 어깁니다.

스스로 확인

간식 나누기 순서도에서 마름모를 지우면 어떤 일이 벌어질까요? 문법 오류 · 실행 오류 · 논리 오류 가운데 어느 것이 되는지까지 말해 보세요.

같은 답, 다른 방법

둘 다 맞는 답을 낸다면, 무엇을 보고 고를까요?

한 문제에 알고리즘이 하나만 있는 것이 아닙니다. 1부터 100까지 모두 더하기를 예로 봅시다. 두 방법 모두 답은 5050으로 같습니다.

가 — 하나씩 더한다

합에 0을 넣는다.
수에 1을 넣는다.
합에 수를 더한다.
수를 1 늘린다.
수가 100보다 크지 않으면 3번으로 돌아간다.
합을 알린다.

더하기를 100번 합니다.

나 — 짝을 지어 센다

1과 100을 더하면 101이다.
2와 99, 3과 98…도 모두 101이다.
그런 짝이 50개 있다.
101 × 50 = 5050을 알린다.

계산을 세 번 합니다.

100까지라면 둘 다 순식간입니다. 그런데 1부터 1억까지라면 이야기가 달라집니다. 「가」는 더하기를 1억 번 하지만 「나」는 여전히 세 번입니다. 알고리즘을 비교할 때 가장 먼저 보는 것은 문제가 커질 때 일이 얼마나 늘어나는가입니다.

그렇다고 「나」가 언제나 낫지는 않습니다

「나」는 1부터 차례로 이어지는 수를 더할 때만 쓸 수 있습니다. 적힌 네 줄 그대로는 끝수가 짝수일 때만 통합니다. 끝수가 홀수이면 가운데 수 하나가 짝을 찾지 못해 따로 더해야 합니다. 중간에 몇 개를 빼거나 아무 수나 늘어놓으면 짝이 맞지 않아 아예 쓸 수가 없습니다. 「가」는 어떤 수가 늘어서 있든 통합니다. 빠른 방법일수록 쓸 수 있는 조건이 좁은 경우가 많습니다.

그래서 비교할 때 함께 보는 것들

얼마나 걸리는가 — 문제가 커질 때 일이 얼마나 늘어나는지
얼마나 쓰는가 — 값을 담아 둘 자리를 얼마나 차지하는지. 빠른 대신 자리를 많이 쓰는 방법이 흔합니다
어디까지 통하는가 — 특별한 조건에서만 되는지, 어떤 경우에도 되는지
읽을 수 있는가 — 남이 고칠 수 있는지. 빨라졌지만 아무도 못 읽는 알고리즘은 유지 보수에서 대가를 치릅니다

네 가지가 서로 부딪히기 때문에 「가장 좋은 알고리즘」은 상황마다 다릅니다.

스스로 확인

시험 점수 서른 개의 합을 구해야 합니다. 「가」와 「나」 중 어느 것을 써야 할까요? 「어디까지 통하는가」를 근거로 답해 보세요.

핵심 정리

알고리즘

algorithm

문제를 푸는 방법을 단계로 나누어 순서대로 적은 것
간식 나누기의 푸는 순서 여섯 줄도 알고리즘이다
알고리즘 하나로 여러 언어의 프로그램을 만들 수 있다

갖춰야 할 다섯

빠지면 알고리즘이 아니다

입력 0개 이상 · 출력 1개 이상 — 입력만 없어도 된다
명확성 한 가지로만 읽힌다 · 유한성 반드시 끝난다
수행 가능성 실제로 해낼 수 있는 일이어야 한다

적는 세 방법

쓰임이 다르다

자연어 누구나 읽는다 — 처음 순서를 잡을 때
의사코드 짧고 또렷하다 — 코드로 옮기기 직전
순서도 타원 · 평행사변형 · 직사각형 · 마름모로 흐름을 그린다

무엇이 더 나은가

상황마다 다르다

먼저 보는 것은 문제가 커질 때 일이 얼마나 늘어나는가
걸리는 시간 · 쓰는 자리 · 통하는 범위 · 읽을 수 있는가
빠른 방법일수록 쓸 수 있는 조건이 좁은 경우가 많다

확인 퀴즈

배운 내용을 확인해 봅시다.

Q1

「1부터 시작해 1씩 더해 가며 계속 화면에 보여 준다」가 어기고 있는 조건은?

Q2

순서도에서 마름모가 뜻하는 것은?

Q3

알고리즘에 대한 설명으로 옳지 않은 것은?