스크래치 프로그래밍 맛보기

무엇이 더 많은가

스크래치는 MIT 대학교에서 2007년에 만든 교육용 프로그래밍 언어다. 다른 프로그래밍 언어와 달리 마치 레고 블록을 쌓듯 프로그램을 만들 수 있어 배우기 쉽다. 스크래치 홈페이지(scratch.mit.edu)에서 직접 프로그램을 만들 수 있고, 오프라인 버전을 다운로드 받아 사용할 수도 있다.

먼저 내가 지은 “원시인 부족 이야기”를 읽어보자.

원시인 부족 이야기
옛날 옛적 빙하기 시절에 어느 원시인 부족이 살았다.
눈과 얼음으로 뒤덮인 산에는 먹을게 아무 것도 없었는데 다행히도 전설로만
전해지는 신기한 바구니가 하나 있었다. 전설에 따르면 바구니에는 매일 아침마다
사과와 배가 채워지는데, 바구니 안에 어느 과일이 더 많이 들어있는지 맞히면
그 과일들을 모두 먹을 수 있지만, 틀리면 바구니가 낭떠러지 밑으로 떨어져서
다시는 과일을 먹을 수 없게 된다.
불행하게도 그 원시인 부족은 수에 대해 전혀 모른다. 따라서 수를 셀 수도 없고
수를 비교할 줄도 모른다. 원시인 부족은 주변에 다른 음식이 없기 때문에 살아남기
위해서는 과일을 매일 먹어야 한다. 주변에 기다란 막대기들이 있는데
여기에 어떤 표시를 할 수 있다.
원주민 부족은 이 막대기를 사용해서 어느 과일이 더 많은지 알아 맞히려고 한다.

이제 스크래치로 이 문제를 해결해 보자. 긴 막대기는 스크래치의 리스트라고 생각하면 된다. 리스트 안에 수를 기록하거나 두 수를 비교할 수는 없다(하지만 리스트의 인덱스 번호는 사용할 수 있다). ‘바구니’라는 리스트가 하나 주어지는데, 그 안에 “사과, 배, 배, 배, 사과, 배, …”와 같이 임의의 순서로 입력 값이 주어진다.

막대기 두 개를 사용하는 방법

바구니 안에 사과와 배가 섞여 있으므로 한 막대기는 사과, 다른 막대기는 배를 표시하기 위해 막대기 두 개를 준비한다. 막대기 두 개 모두에 맨 처음이라는 표시로 ‘-’를 하나 긋는다. 그런 다음에 바구니에서 과일을 하나씩 꺼내면서 그 과일에 해당하는 막대기에 ‘O’를 하나씩 추가한다. 바구니가 비게 되면 사과와 배 막대기에서 ‘O’를 하나씩 지운다. 그러다가 한 막대기의 마지막이 ‘-’가 나오면 ‘O’를 지우는 작업을 중단한다. 만약 사과 막대기에 ‘-’만 남아 있으면 배가 더 많은 것이고, 배 막대기에 ‘-’만 남아 있으면 사과가 더 많은 것이다. 그리고 두 막대기 모두 ‘-’만 남아 있다면 두 과일의 개수는 같은 것이다. <그림 1>은 이 방법을 프로그램으로 만든 것이다.

문제 만들기

위에서 만든 프로그램이 맞았는지 검사해 보려면 바구니에 데이터가 있어야 한다. 우리가 직접 데이터를 넣어줄 수 있지만 여러 가지 데이터로 맞았는지 검사하려면 힘들기 때문에 데이터를 만들어 주는 프로그램을 만들었다. <그림 2>를 보면 [1부터 2사이의 난수] 블록이 있는데 이 블록을 실행하면 컴퓨터가 1과 2 중에서 아무 수나 하나 만든다. 만약 1이 나오면 바구니에 ‘사과’를 넣고, 2가 나오면 바구니에 ‘배’를 넣는다. 이런 작업을 여러 번 반복하면 바구니에 사과와 배가 섞여서 들어가게 된다. 프로그램을 실행해보면 <그림 3>과 같이 올바른 답이 나온 것을 확인할 수 있다.

막대기 하나로 해결하기

앞에서는 사과와 배, 두 개의 막대기를 사용했다. 그런데, 두 개의 막대기가 모두 필요할까 만약 막대기가 하나만 있다면 어떻게 알 수 없을까


만약 막대기가 하나만 있다면 <그림 4>의 방법으로 바꿔 문제를 해결할 수 있다. 이 방법은 막대기의 위부터는 사과를, 아래부터는 배를 기록한 다음에 비교하는 방법이다. 비교는 양끝을 계속 지우다가 무엇이 먼저 바닥나는지 알아보면 된다. 만약 동시에 둘 다 바닥이 나면 사과와 배의 개수가 같다는 뜻이 된다. <그림 1>의 프로그램에서는 바구니의 길이와 같은 크기의 막대기를 두 개 사용했는데, <그림 4>의 프로그램에서는 같은 크기의 막대기를 사용하면서도 한 개만으로 해결할 수 있다는 장점이 있다. 그런데, 지금처럼 막대기를 하나만 사용하면서 좀 더 빠르게 알아낼 수 있는 방법이 있을까

스택(Stack) 구조를 이용해 해결하기

컴퓨터에 스택이라는 것이 있는데, 이것은 한쪽에서만 데이터가 들어가고 나오는 구조다. 스택에서 데이터를 추가하는 것을 푸시(push), 하나 빼는 것을 팝(pop)이라고 한다. 스택 자료구조를 이용하면 이 문제를 쉽게 풀 수 있다. 막대기를 스택으로 보고 막대기가 비어 있을 때에는 바구니에서 꺼낸 과일 이름을 막대기에 넣는다(push). 만약 막대기가 비어 있지 않을 때에는 바구니에서 꺼낸 과일과 막대기에 표시된 과일이 같으면 그 과일 이름을 한 번 더 추가하고(push), 같지 않다면 막대기에서 하나를 지운다(pop). 이 과정을 바구니가 빌 때까지 계속 한 다음에 막대기에 남아 있는 과일이 더 많은 과일이다. 만약 막대기가 비어 있다면 두 과일의 개수는 똑같은 것이다. <그림 5>는 스택을 이용해 프로그램을 만든 것이다. 스크래치에는 스택 블록이 따로 없으므로 스택의 기능을 직접 만들어주어야 한다. 그런데, 이 방법이 왜 <그림 4>의 방법에 비해 더 빠를까 <그림 4>는 하나씩 넣는 과정과 하나씩 빼는 과정이 있어서 두 번 도는데 비해서 <그림 5>의 방법은 한 번만 돌면서 넣거나 빼기 때문에 속도가 두 배 빠르다고 볼 수 있다.


<그림 5>의 스크래치 프로그램을 C++로 만들면 <리스트 1>과 같이 된다. 일부러 숫자를 하나도 사용하지 않고 프로그램을 만들었다.

<리스트 1> Stack 구조를 이용한 방법 (C++ 버전)#include < iostream>
#include < cstdio>
#include < stack>
using namespace std;int i;
string a, ans;
stack< char> st;
int main() {
freopen("input.txt", "r", stdin);
cin >> a;
for (; a[i]; i++) {
if (st.empty()) st.push(a[i]);
else {
if (a[i] == st.top()) st.push(a[i]);
else st.pop();
}
}
if (st.empty()) ans = "same";
else ans = st.top();
cout < < ans < < endl;
}

한꺼번에 두 개씩 읽는 방법

<그림 5>의 방법을 더욱 빠르게 할 수 있는 방법이 있다. 바구니에서 꺼낼 때 한 번에 하나씩 꺼내는 대신에 두 개씩 꺼내면 더 빠르게 할 수 있다. 꺼낸 두 개가 다르면 결과에 영향을 미치지 않기 때문에 무시하고 다시 두 개를 꺼낸다. 두 개의 과일이 서로 같을 때에는 <그림 5>와 같이 스택을 사용한다. 즉, 막대기가 비어있거나 같은 과일이 있으면 추가(push), 막대기에 다른 과일이 있으면 삭제(pop)를 하면 된다. <그림 5>의 방법과 마찬가지로 막대기에 남은 과일이 더 많은 과일이 되고, 막대기에 남은 과일이 없다면 두 과일의 개수는 같은 것이다. <그림 6>의 방법은 바구니에서 꺼낸 두 개가 서로 다른 과일일 때 하는 일이 아무 것도 없으므로 <그림 5>의 방법보다 빠르게 된다. 얼마나 빠른지 테스트 하기 위해서 관찰 그룹의 [타이머 초기화] 블록을 시작하는 부분에, [시간을 타이머로 정하기] 블록을 끝부분에 넣으면 ‘시간’이라는 변수에 프로그램이 실행된 시간이 초 단위로 저장된다. <표 1>은 지금까지 설명했던 네 가지 방법의 실행시간을 비교한 것이다. <그림 6>의 두 개씩 읽는 방법은 실행시간이 가장 빨랐던 <그림 5>의 방법보다 거의 두 배나 빠르다. 필요한 공간도 최대 절반만 사용하기 때문에 지금까지 소개한 방법 중에서 가장 좋은 방법이라고 할 수 있다. 참고로 C++로 만들면 무엇이 더 많은지 결과를 훨씬 빨리 알아낼 수 있다. <리스트 1>의 프로그램으로 시간을 재면 과일개수가 10,000개 일 때는 0.002초, 1,000,000개 일 때는 0.267초가 걸린다.




‘무엇이 더 많은가’ 프로그램은 scratch.mit.edu/projects/7665 2488/에서 실행해 볼 수 있고 프로그램 소스코드를 볼 수 있다.

출처 : 마이크로소프트웨어 10월호

제공 : 데이터 전문가 지식포털 DBguide.net