알고리즘과 표현

문제를 풀 방법을 떠올렸다고 해서 문제가 저절로 풀리지는 않습니다. 그 방법이 내 머릿속에만 있으면 나 말고는 아무도 쓸 수 없기 때문입니다. 친구에게 설명하려면 말로 옮겨야 하고, 컴퓨터에게 시키려면 컴퓨터가 읽을 수 있는 형태로 옮겨야 합니다.

「알고리즘」은 9세기 무렵에 활동한 수학자 알콰리즈미(al-Khwarizmi)의 이름에서 온 말입니다. 그는 계산 문제를 정해진 절차를 따라 푸는 방법을 정리한 사람으로 알려져 있습니다. 말의 뿌리에 이미 「정해진 절차」라는 뜻이 들어 있는 셈입니다.

사실 우리는 알고리즘을 이미 매일 쓰고 있습니다. 조리법, 가구 조립 설명서, 준비 운동 순서가 모두 그렇습니다. 이들의 공통점은 할 일이 순서대로 적혀 있고, 그 순서대로 따라 하면 누구나 같은 결과에 이른다는 것입니다.

집에 있는 동생에게 심부름을 시킨다고 해 봅시다. 나는 곧 나가야 해서 쪽지 한 장만 남길 수 있습니다. 옆에서 「그거 말고 저거」라고 거들어 줄 수 없으니, 동생이 그 쪽지만 보고 끝까지 해낼 수 있게 적어야 합니다.

컴퓨터에게 일을 시키는 것이 딱 이 쪽지와 같습니다. 컴퓨터는 되묻지 않고, 눈치도 보지 않습니다. 그래서 쪽지가 갖추어야 할 것이 그대로 알고리즘이 갖추어야 할 것이 됩니다.

이 다섯 가지에는 각각 이름이 붙어 있습니다. 차례대로 수행 가능성 · 입력 · 출력 · 명확성 · 유한성이며, 다섯을 모두 갖추어야 알고리즘이라고 부를 수 있습니다. 각 조건이 무엇을 요구하는지는 그 조건을 어긴 절차를 함께 보면 훨씬 또렷해집니다.

알고리즘을 적는 방법은 하나가 아닙니다. 흔히 쓰는 것만 꼽아도 자연어와 의사코드, 그리고 순서도가 있습니다. 셋은 서로 다른 알고리즘이 아니라 같은 알고리즘을 적는 세 가지 방식입니다. 「가로와 세로를 받아 직사각형의 넓이를 구해 알려 주는」 하나의 알고리즘을 세 가지로 적어 보겠습니다.

알고리즘 시작
    가로 ← 입력받은 값
    세로 ← 입력받은 값
    넓이 ← 가로 × 세로
    넓이를 출력
알고리즘 끝

순서도의 힘은 기호의 모양에 뜻을 실어 둔다는 데서 나옵니다. 글을 읽지 않고 모양만 살펴봐도 「여기서 값을 받고, 저기서 흐름이 나뉘는구나」가 보입니다. 그러려면 정해진 모양을 정해진 뜻으로만 써야 합니다. 내 마음대로 모양을 바꾸면 그림을 읽는 사람이 오히려 헷갈립니다.

1. 전체 흐름이 위에서 아래로, 나뉠 때는 왼쪽에서 오른쪽으로 가도록 배치합니다.
2. 기호 안에 무슨 일을 하는지를 짧게 적습니다. 기호 밖에 설명을 늘어놓지 않습니다.
3. 약속된 기호만 씁니다. 새 모양을 만들어 쓰지 않습니다.
4. 흐름선이 서로 엇갈리지 않게 합니다. 엇갈리면 어디로 가는 선인지 알 수 없습니다.
5. 시작과 끝, 그리고 나뉘는 곳과 되돌아오는 곳를 분명히 드러냅니다.

알고리즘에서 다음에 무엇을 할지 정하는 짜임을 제어 구조(control structure)라고 합니다. 제어 구조에는 순차 구조, 선택 구조, 반복 구조 세 가지가 있습니다. 아무리 긴 알고리즘이라도 이 셋을 엮은 것으로 볼 수 있습니다.

셋의 차이를 보기 위해, 하루 걸음 수를 다루는 상황을 예로 들어 보겠습니다. 하루 목표를 8000보로 정했다고 해 봅시다. 이 목표 값은 설명을 위해 우리가 정한 숫자입니다.