파이썬으로 하는 알고리즘 교육

 

파이썬으로 하는 알고리즘 교육

파이 차우(Pai H. Chou)
한글판 johnsonj 2006.12.18 원문위치

Department of Electrical and Computer Engineering, University of California, Irvine, CA 92697-2625 USA
chou@ece.uci.edu

초록

알고리즘의 설계와 분석은 컴퓨터 공학과 엔지니어링 교육 분야에서 기초적인 주제이다. 많은 알고리즘 강좌에서 학생들이 알고리즘을 더 잘 이해할 수 있도록 돕기 위하여 프로그래밍 숙제가 포함된다. 불행하게도, 전통적인 프로그래밍 언어를 사용하면 학생들은 알고리즘 디자인 말고 세부적인 데이터 구조와 지원 루틴을 다루지 않을 수 없다. 파이썬은 알고리즘-지향적 언어를 대표하여 교육에 꼭 필요하게 되었다. 파이썬의 장점에는 그의 교과서적인 구문과 실험을 장려하는 상호작용이 있다. 보다 중요한 것은, 파이썬을 처음 사용한 경험을 보고한다는 것이다. 파이썬을 사용하여 간결한 텍스트 형태로 그래프와 흐름 네트워크 같은 집합 데이터 구조를 표현하였다. 이 덕분에 학생들은 자신감을 가지고 알고리즘을 실험할 뿐만 아니라 극적으로 개발 시간이 절감된다. 이런 특징들은 졸업생 수준의 알고리즘 강좌에서 구현되어 성공적인 결과를 얻었다.

1. 들어가는 말

컴퓨터 프로그램을 작성해서 문제를 풀어야 하는 자에게 알고리즘은 가장 중요한 도구입니다. 알고리즘은 컴퓨터 과학자와 컴퓨터 공학자가 사용할 뿐만 아니라, 수 많은 기타 공학과 과학도들이 사용합니다. 결과적으로, 알고리즘 강좌는 컴퓨터 학도들에게 필수 과목일 뿐만 아니라, 다른 분야의 학생들에게도 필수 과목입니다.

그냥 교과서를 읽고 문제를 풀어 보기만 해도 알고리즘을 배울 수 있지만, 학생들은 종종 실제로 구현해보기 전까지는 진짜로 알고리즘을 배우지 못합니다. 결과적으로, 알고리즘 강좌가 프로그래밍 숙제에 포함되지 않는 경우는 드뭅니다. 프로그래밍을 알고리즘 교육의 필수 부분으로 포함한 교과서는 이 요구를 충족시키기 위하여 저작됩니다 [4]. 사실상 모든 강좌와 교과서가 지금까지 학생들에게 C나 C++ 같은 전통적인 언어로 프로그래밍하기를 요구해 왔습니다. 그리고 최근 자바가 인기를 얻었습니다 [5]. 이런 언어들을 사용하자는 주장은 주로 실용적인 이유 때문입니다: 학생들은 이미 이런 언어에 통달했을 수도 있습니다; 그렇지 않다고 할지라도, 이런 언어들을 배우면 실용적 기술을 얻을 것입니다.

1.1 프로그래밍 vs. 알고리즘 디자인

불행하게도, 경험에 미루어 보면 알고리즘 수업시간의 프로그래밍 숙제가 언제나 교육적으로 이익인 것은 아닙니다. 대부분의 알고리즘이 교과서의 몇줄에서 반페이지에 불과하지만, 그의 구현은 종종 C나 Java로 수백줄을 요구하기도 합니다. 한가지 이유는 이런 언어들이 전역 변수와 지역 변수 그리고 매개변수들을 먼저 선언해야 사용이 가능하기 때문입니다. 보다 중요한 또다른 이유는 리스트와 연결 데이터 구조 그리고 특화된 배열 같은 많은 데이터 구조가 그 알고리즘을 지원하기 위하여 구현되고 디자인되어야 하기 때문입니다. 그리고 이런 연습상의 복잡성은 그래프나 흐름 네트워크 같은 군집 데이터 구조가 관련되면 빠르게 증가합니다. 사실, 대부분의 객체-지향적 프로그래머들은 대부분의 노력을 클래스와 인터페이스를 설계하는데 소비합니다. 그리고 상대적으로 적은 시간을 메쏘드를 위한 코드를 채우는데 소비합니다. 결과적으로, 이런 프로그래밍 숙제 때문에 학생들은 대부분의 시간을 알고리즘 문제가 아니라 프로그래밍 문제에 소비하지 않을 수 없습니다. 컴퓨터 도사가 아닌 학생들은 심각하게 불리한 상황에 처하는 경향이 있습니다.

어떤 교사들은 학생들에게 데이터 구조를 위한 라이브러리 루틴을 제공함으로써 이런 부담을 덜어주려고 시도합니다. 그렇지만, 입력/출력과 재사용을 포함하여 여전히 많은 문제들이 이런 전통적인 언어에 내재합니다. 예를 들어, 라이브러리는 먼저 트리나 그래프를 구축하는데 필요한 API를 제공해야만 데이터 구조로 알고리즘을 요청할 수 있습니다. 학생들은 테스트 사례를 코드에 직접 짜 넣어야 하는데, 이 때문에 그래프에 한 번에 노드 하나를 추가하기 위해 연속적으로 호출해야 합니다. 또는 파일로부터 그래프의 기술을 읽어야 합니다. 앞의 접근법은 엉성해 보일 수 있는데, 그 이유는 소스 코드가 데이터 구조를 닮지 않았지만 그 의미는 그 API에 묶여 있기 때문입니다. 맞춤 언어를 사용하여 그래프를 표현하는, 뒤의 접근법이 아마도 더 간결하겠지만, 해석 루틴을 요구하기 때문에 재사용과 확장성이 떨어질 수 있습니다. 예를 들어, 처음에는 비가중 그래프를 정의했다가 나중에 가중 그래프를 원하는 경우를 생각해 봅시다. 가중치 확장에 대하여 서브클래스를 만드는 것이 쉬울 수 있지만, 가중 사례와 비가중 사례를 처리하기 위하여 해석기도 바꾸어야 합니다. 그리고 가중치를 다시 터플이나 문자열 또는 임의의 집합으로 확장하고 싶다고 합시다: 그 때마다 해석기를 매번 바꾸어야 합니다.

1.2 파이썬의 장점

파이썬은 이런 문제들에 접근하여 알고리즘 교육에 매력적인 언어가 됩니다. 첫째, 들여쓰기-기반의 구문이 대부분의 교과서와 비슷하여 별 프로그래밍 배경이 없는 학생들조차 문제없이 책을 따라 가면서 바로 알고리즘을 코딩할 수 있습니다. 그러므로, 다른 언어와의 인기 논쟁은 무의미합니다. 특히 파이썬의 상응 모드는 학생들이 지루한 컴파일 주기 없이 실험을 하도록 장려합니다. 둘째, 파이썬은 리스트, 터플, 그리고 사전 같이 알고리즘에서 직접 사용할 수 있는 기본 데이터 구조를 제공합니다. 트리와 그래프 같은 더 복잡한 데이터 구조도 파이썬으로 간결하게 인간이-읽을 수 있는 형태로 표현할 수 있습니다. 그런 데이터 구조를 재고 안할 필요가 없습니다. 예를 들어, 섹션 5에서는 가중 그래프를 정점으로 구성된 사전으로 표현하는 새로운 방법을 보여주겠습니다. 그의 인접 리스트는 간선 가중치의 사전으로 표현됩니다. 여러가지 장점이 있습니다: 그 알고리즘들에 대한 테스트 사례는 파이썬으로 직접 작성할 수 있습니다. 데이터-구조-구축 API를 호출할 필요도 없고, 맞춤 해석기에 의존할 필요도 없습니다. 게다가, 임의 데이터 유형으로 무한대로 확장이 가능합니다. 파이썬은 그냥 그것들을 건네기만 할 뿐, 필요할 때까지 데이터 유형을 해석하지 않습니다. 언제든지, 데이터 구조는 파이썬과 사람이 읽을 수 있는 텍스트 형태로 표시가 가능합니다.

이 논문은 지금부터 졸업생 수준의 알고리즘 수업에 파이썬을 배치해서 얻은 성공 경험담을 보고하고자 합니다. 학생들은 적극적으로 받아들였을 뿐만 아니라 자신만의 연구 분야에서 문제를 푸는데 도움을 줄 귀중한 도구를 얻었습니다. 다음 섹션에서는 수업시간에 보여준 것과 똑 같은 과정으로, 어떻게 알고리즘을 파이썬으로 가르치는지 보여줍니다. 정렬 알고리즘 그리고 선점 큐를 가진 힙정렬로부터 시작하여 메모리 관리 문제들을 다룹니다. 다음, 그것들을 사용하여 이진 트리를 구축하고 허프만 알고리즘을 구현하겠습니다. 마지막으로, 파이썬이 어떻게 효과적으로 그래프 알고리즘에 사용되는지 보여주겠습니다.

2. 첫 수업: 정렬

대부분의 교과서는 알고리즘과 복잡도 분석을 소개하는 한 가지 방법으로 정렬로 시작합니다. 정렬 알고리즘을 사용하면서 파이썬도 제일 첫 시간부터 소개합니다. 우리의 전략은 알고리즘을 파이썬 코드와 일대일 코드로 대비하여 그 유사성을 보여주는 것입니다. InsertionSort부터 시작하겠습니다. 이 정렬은 정렬된 배열을 앞에서부터 한 번에 하나씩 증가시킵니다. 처음에, A[1] (교과서형임; 파이썬으로는 A[0]의 형태임)는 이 서브배열의 유일한 요소이며 손쉽게 정렬됩니다. for-회돌이를 반복할 때마다 다음 새 요소가 정렬된 서브배열에 삽입되는데 그 요소들은 서로에 대하여 상대적으로 정렬됩니다; 이것은 BubbleSort와 대조적인데, 이 정렬은 반복할 때마다 새로운 요소를 자신의 절대적인 정렬 위치에 배치합니다.

교과서의 알고리즘 [1]

Insertion-Sort(A)
1 for j <- 2 to length[A]
2      do key <- A[j]
3            i <- j - 1
4            while i > 0 and A[i] > key
5                   do A[i+1] <- A[i]
6                         i <- i - 1
7             A[i + 1] <- key

파이썬 코드

def InsertionSort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while (i >=0) and (A[i] > key):
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key

일단 학생들이 비슷하다고 인식하면, 대부분의 프로그래밍 공포는 간단히 사라집니다. 또한 파이썬의 상호대화적인 본성을 보여주는 데에도 도움이 됩니다. 컴퓨터 프로젝터를 사용하고 실제로 프로그램에 타자를 해보면, 기껏해야 길이가 8줄일 뿐입이다. 제일 좋은 것은, 그냥 테스트 사례를 리스트의 형태로 타자해 넣기만 하면 그 알고리즘을 테스트할 수 있다는 것입니다:

>>> x = [2,7,3,8,1]   # 테스트 사례를 만든다
>>> InsertionSort(x)   # 루틴을 호출한다
>>> x        # 결과를 본다
[1, 2, 3, 7, 8]

어떤 면에서, 파이썬은 교과서에 알맞습니다. 교과서에 제시된 알고리즘은 더 이상 의사 코드가 아니기 때문입니다. 즉 이론적인 흥미만을 만족시키는 단계가 더 이상 아니기 때문입니다; 만든 데이터를 사용하여 실제로 알고리즘을 실행하기가 얼마나 쉬운지 볼 수 있습니다. 사실, 같은 코드가 아무 변경없이 문자열과 터플 등등을 비롯하여 다른 데이터 유형에도 똑 같이 잘 작동하는 것도 볼 수 있습니다. 정렬은 좋은 시작 예제입니다. 복잡한 메모리 관리가 필요없이 구조가 직접 맵핑될 뿐만 아니라(나중에 상술함), 또 그 대등한 의미구조도 역시 일치하기 때문입니다: 스칼라 값은 값으로 건네지는 반면, 배열은 참조로 건네집니다.

3. 힙 정렬 그리고 선점 큐

계속해서 힙 정렬과 선점 큐를 소개하겠습니다. 힙은 배열 A[1..n]를 사용하여 근사 균형 이진 트리를 나타내는 데이터 구조입니다. 한 A[i] 요소의 좌우 자손은 각각 위치가 A[2i], A[2i+1]이고, A[i] >= A[2i], A[2i+1]입니다. 힙 정렬은 배열의 뒤(back)에서부터 앞쪽으로 한 번에 한 요소씩 가장 큰 요소를 힙의 앞에서 추출함으로써 정렬된 서브배열을 구축합니다. 처음 정렬 부분은 비어 있습니다. 그리고 BuildHeap를 호출하면 A[1..n]이 힙으로 바뀝니다. 힙 부분은 가장 큰 요소를 A[1]에 두기 때문에, 첫 반복에서 그 요소를 뽑아 그의 올바른 정렬 위치인 A[n]에 배치합니다. 다음 반복에서 (또 A[1]로부터) 다음으로 큰 요소를 추출하여 그것을 A[n-1]에 두고, 등등, A의 모든 요소가 정렬될 때까지 계속됩니다. 매 추출 단계마다 Heapify가 호출되는데 주목합시다. 이는 A[1]과 A[h]를 바꾸면, A[1..h-1]가 힙 특성을 더 이상 만족시킬 수 없기 때문입니다. 그러나 여전히 "거의" 힙이기 때문에 -- 다시 말해, 루트 위치가 여전히 하부힙이라는 점만 빼면 모든 것이 힙입니다 -- Heapify를 호출하면 그 힙을 O(h) 시간에 재구축할 필요없이 O(lg h) 시간에 효율적으로 수정이 가능합니다.

한가지 차이점은 교과서의 알고리즘이 1-기반의 배열 지표를 가정하는 반면, 파이썬은 0-기반의 배열을 가정한다는 것입니다. 지표 조정 때문에 일어나는 에러를 피하기 위하여, 학생들에게 A[0]에 None을 집어 넣으라고 요구했습니다. 그리고 대신에 배열크기를 n+1 부터 사용하라고 요구했습니다. 파이썬 코드는 다음과 같습니다

def Parent(i): return i/2
def Left(i): return 2*i
def Right(i): return 2*i+1

def Heapify(A, i, n): # A는 "거의 힙이다" (루트만 빼면); 모든 A가 힙이 되도록 수정한다
    l = Left(i)
    r = Right(i)
    if l <= n and A[l] > A[i]: largest = l
    else: largest = i
    if r <= n and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        Heapify(A, largest, n)

def HeapLength(A): return len(A)-1
def BuildHeap(A): # 미정렬된 배열로부터 힙 A를 구축한다
    n = HeapLength(A)
    for i in range(n/2,0,-1):
        Heapify(A,i,n)

def HeapSort(A): # 힙을 사용하여 끝에서부터 정렬된 배열을 구축한다
    BuildHeap(A)
    HeapSize=HeapLength(A)
    for i in range(HeapSize,1,-1):
        A[1],A[i]=A[i],A[1] # 가장 큰 요소는 힙의 루티이다. 그것을 배열의 끝에 두자
        HeapSize=HeapSize-1 # 다음 큰 요소를 얻기 위해 힙 크기를 1 줄인다
        Heapify(A,1,HeapSize)

힙과 선점 큐는 밀접한 관련이 있습니다. 힙은 선점 규를 O(lg n)-시간 삽입과 추출로 효율적으로 구현할 수 있습니다. 그렇지만, 한 가지 차이점은 동적 메모리 관리입니다: 힙 정렬에서 배열의 크기는 여전히 같습니다. 반면, 선점 큐에서, 큐의 크기는 늘어나고 줄어듭니다. 이 기회를 이용하여 두 가지 구조를 소개합니다. 첫 째, A.append()과 A.pop() 을 사용하면 A 리스트를 늘이고 줄일 수 있으며, len(A)는 그 리스트의 현재 길이를 돌려준다는 것을 보여줍니다. 둘째, 언더플로우(underflow)의 경우 (그리고 원한다면 오버플로우(overflow)의 경우), 예외를 일으키고 잡는 법을 학생들에게 보여줍니다. 이런 구조들은 파이썬에만 유일한 것은 아니지만, 파이썬에서는 쉽게 실험해 볼 수 있습니다.

4. 이진 트리와 허프만 인코딩

선점 큐를 확보했으므로, 학생들에게 즉시 흥미로운 알고리즘들을 구현하도록 시킬 수 있습니다. 여기에는 다익스트라(Dijkstra)의 단일-소스 최단 경로 그리고 프림(Prim)의 최소-신장 트리가 포함됩니다. 다음 주제는 탐욕적 알고리즘으로서, 학생들에게 파이썬으로 허프만(Huffman) 인코딩을 구현하라고 요구합니다. 기억을 되살려 보면, 허프만 알고리즘은 각 문자의 발생 빈도에 근거하여 접두사-없는, 가변-길이의 코드 워드(code words)를 생산합니다. 자주 사용되는 문글자는 더 짧은 길이의 비트 문자열로 인코드됩니다. 반면에 좀 덜 사용되는 글자는 더 긴 길이의 비트 문자열로 인코드됩니다. 탐욕 알고리즘은 선점 큐를 사용하여 가장 덜 나타나는 (단말 또는 내부의) 두 노드를 추출해서, 가중치가 두 자손의 합인 새로운 노드를 할당합니다. 그리고 그 새로운 노드를 다시 선점 큐에 삽입합니다. 탐욕 알고리즘은 선점 큐가 마지막 노드를 제거할 때 끝납니다. 마지막 노드가 허프만 트리의 루트가 됩니다. 각 글자에 대한 비트 문자열은 그 허프만 트리를 순회하면 얻을 수 있습니다. 왼쪽 가지를 취하면 결과는 `0'이고, 오른쪽 가지를 취하면 결과는 `1'입니다.

예를 들어, 다음과 같은 빈도로 입력 문자 세트가 출현한다고 가정해 봅시다

• 'a': 45%
• 'b': 13%
• 'c': 12%
• 'd': 16%
• 'e':   9%
• 'f':   5%

허프만 알고리즘은 최소로 출현하는 두 요소를 반복적으로 큐에서 제거하고, 가중치가 자손의 합과 같은 새로운 내부 노드를 만들어서, 그것을 선점 큐에 삽입하여 트리를 구성합니다. 그 결과는 각 문자에 대하여 가변-길이의 코드가 정의된 트리입니다 (그림. 1). 왼쪽 가지는 꼬리표가 0이고, 오른쪽 가지는 꼬리표가 1이며, 각 문자에 대한 허프만 코드는 그냥 루트에서 단말로 가는 경로 꼬리표로 구성된 문자열입니다. 예를 들어, 그 인코딩은 다음과 같습니다.

• 'a': 0
• 'b': 1 0 0
• 'c': 1 0 1
• 'd': 1 1 0
• 'e': 1 1 1 0
• 'f': 1 1 1 1

Fig.1 허프만 트리의 예

이미 선점 큐가 있기 때문에, 빠진 것은 특별한 이진 트리입니다. 요구조건은 다음과 같습니다.

• 단말 노드는 인코드되는 글자와 그의 출현빈도를 표현할 수 있어야 합니다..
• 내부 노드는 자손이 둘 이어야 하며, 또한 가중치가 두 자손의 합과 같아야 합니다.
• 선점 큐는 단말 노드와 내부 노드를 큐에 삽입하고 제거할 수 있어야 하며 가중치에 근거하여 그 노드들을 비교할 수 있어야 합니다.

이것을 전통적인 언어인 C 또는 Java로 구현했다면, 학생들에게 weight라는 이름의 필드를 가진 구조나 클래스를 정의하는 법을 가르쳐야 했을 것입니다; 단말 노드는 character 필드가 필요합니다. 한편으로 내부 노드는 leftchild 필드와 rightchild 필드를 요구합니다. 선점 큐는 그 둘을 비교할 수 있어야 하기 때문에, 필연적으로 내장된 비교 연산자를 사용하는 대신에 적절한 비교 메쏘드를 호출하도록 선점 큐를 수정해야 할 것입니다. 그리고 단말 노드와 내부 노드 모두 같은 클래스 안에 있어야 하거나 또는 그 비교 메쏘드가 구현된 클래스의 하부 클래스여야 합니다. 일단 정의했으면, 학생들은 그 허프만 트리를 올바로 구성했는지 알아볼 수 있기를 원할 것입니다. 그렇지만, 기존의 어떤 디버거도 자동으로 그 노드를 모아 트리로 인쇄하는 법을 알지 못합니다. 그러므로, 학생들은 인쇄 루틴을 작성해야 하는 부담이 있습니다. 이것은 실제로 좀 까다로울 수 있으며 또다른 큰 버그의 근원이 될 수 있습니다. 비슷하게, 학생들이 다른 테스트 사레를 지정하려면, 코드에 직접 집어 넣은 데이터를 수정하고 매번 재컴파일 하거나 또는 추가로 해석 루틴을 작성할 필요가 있을 것입니다. 이것 역시 또다른 에러의 근원이 될 수 있습니다.

파이썬 구현으로는 우아하게 구현할 수 있습니다. 따로 루틴을 작성할 필요가 없으며 트리 노드에 대하여 새로운 클래스나 구조를 정의할 필요가 없습니다. 학생들에게 터플을 사용하여 이진 트리를 표현하라고 요구합니다. Lisp와 비슷하게 말입니다:

• 단말 노드는 (출현빈도, 문자) 터플로 표현됩니다:
  [(45, 'a'), (13, 'b'), (12, 'c'), (16, 'd'), (9, 'e'), (5, 'f')].
• 내부 노드는 중위-우선 3-터플로 표현됩니다: (출현빈도, 왼쪽, 오른쪽): 예를 들어, 그림. 1에서 우-하 하부트리는 아래와 같이 표현이 가능합니다.
  (14, (5, 'f'), (9, 'e'))
  내부 노드로서 가중치가 14%입니다. 왼쪽 자손은 (5, 'f')이며, 오른쪽 자손은 (9, 'e') 입니다.

이 트리는 기능적으로 터플 생성으로 구성되었습니다. 트리 노드 데이터 구조를 사용할 필요가 없으며, 좌/우 자손 포인터를 조작할 필요가 전혀 없습니다. 게다가, 기존의 선점 큐 데이터 구조와 쉽게 사용할 수 있습니다. 전혀 수정이 필요하지 않습니다! 이 때문에 터플은 똑 같은 비교 연산자를 사용하여 사전 편찬 순서로 비교가 가능합니다. 이런 식으로, 다른 정보를 인코드하고 있음에도 불구하고 내부 노드와 단말 노드를 비교할 수 있습니다. 둘 사이의 차이는 단말 노드에 대하여 len() = 2이고, 내부 노드에 대하여 len() = 3이라는 것입니다.

요약해 말하면, 약간만 창조적으로 파이썬을 사용하더라도, 알고리즘과 데이터 구조의 재사용을 최대한 달성할 수 있습니다. 또한 파이썬 구문으로 학생들은 글을 쓰듯이 트리를 기술할 수 있습니다. 파이썬 구문은 최대한 간결하고 확장성이 있어서, 특별한 해석기를 사용할 필요가 없습니다.

5. 그래프 알고리즘

그래프는 G(V,E)입니다. V는 정점 집합이고, 그리고 E는 간선의 집합입니다. 간선의 최대 집합은, V 곱하기 V입니다. 그래프는 여러 표현이 있습니다. 대부분의 알고리즘은 인접 리스트 또는 인접 매트릭스로 표현됩니다. 앞의 것은 |E|가 |V|에 가까운 희소 그래프에 좋고, 뒤의 것은 |E|가|V|²에 더 가까운 농밀 그래프에 좋습니다.

전통적인 시스템 프로그래밍 언어인 C나 Java로 그래프를 구현하려면, 먼저 정점과 간선 그리고 그래프에 대하여 데이터 구조를 정의해야 합니다. 데이터 구조는 정점과 간선의 생성과 삭제에 전방 디자인으로 기여합니다. 그런 데이터 구조의 디자인은 코딩 시간의 쉽게 대부분을 점령하고 쉽게 재사용이 불가능합니다. 주로 그 이유는 이런 데이터 구조가 반드시 그릇(containers)으로 정의되어야 하기 때문입니다. LEDA [3]같은 꾸러미들이 C++ 주형틀로 객체-지향적 소스 코드의 재사용을 개선하려고 노력하고 있지만, 여전히 학생들은 전체 꾸러미를 채택해야만 무엇인가 유용한 일을 하기 시작할 수 있습니다. 그릇은 종종 강력한 정적 유형정의의 문제점들을 우회하기 위하여 디자인 되지만, 그렇게 하면 최종 사용자 코드에서 동적 유형 점검을 재구현해야 합니다. 더 심각한 결점은 C-포인터의 사용이나 Java-참조의 사용 때문에 이런 객체들을 보기가 어색해진다는 것입니다. 디버거가 이런 객체들을 텍스트 형태로 보여줄 수 있지만, 너무 많은 정보도 함께 보여주거나 프로그램에 직접 사용이 불가능합니다.

그래프 데이터 구조에서 강조한 바와 같이 파이썬은 많은 장점들을 제공합니다. 아주 간결한 사전의 사전 구현을 사용하여 인접 배열 리스트 표현으로 그래프를 구현했습니다. 기본적으로 그래프는 파이썬 사전으로 표현됩니다. 그 키는 정점의 문자열 이름이고 각 정점의 이름은 그의 인접 리스트에 짝짓기됩니다. 예를 들어, 그림 2와 같은 그래프를 생각해 시다:

그림 2: 방향 그래프의 예

다음과 같은 파이썬 코드로 표현할 수 있습니다

H = {'A': ['C', 'D'], 'B': ['D', 'A'], 'C': ['D', 'E'],
      'D': ['E'], 'E': [] }

위의 코드는 간단한, 방향성, 비가중 그래프를 표현합니다. 그림. 3과 같은 가중 그래프가 필요하면, 그냥 인접 정점으로 구성된 리스트를 교체하면 됩니다. 인접 정점들을 가중치에 짝짓기한 사전으로 말입니다:

그림 3: 가중 그래프의 예

L = {'A': {'C':2, 'D':6}, 'B': {'D':8, 'A':3},
       'C': {'D':7, 'E':5}, 'D': {'E':-2}, 'E': {}}

정점 V 리스트는 그냥 H.keys() 또는 L.keys()입니다. 인접 리스트는 비가중 그래프에 대하여 H[v]이고, 가중 그래프에 대하여 L[v].keys()입니다. 간선 가중치 w(u,v)는 L[u][v]입니다. 편리하게 프로그래밍하기 위하여, 그 구현 상세를 한 객체 안으로 싸 넣을 수 있습니다.

class Graph:
   def __init__(self, g):
      self.g = g
   def V(self):
      return self.g.keys()
   def Adj(self,v):
      return self.g[v].keys()
   def w(self,u,v):
      return self.g[u][v]

G = Graph(L)로 그래프 객체를 만들 수 있습니다. 이런 접근법의 장점에는 간결한 텍스트 형태와 확장성이 포함됩니다. 첫째, 실제로 설계해야할 데이터 구조가 없습니다. 그래프의 텍스트적 표현은 파이썬 실행파일입니다. 학생은 이 구조를 상호대화적으로 타자해 넣을 수 있습니다. 특별한 그래프 편집기를 사용하지 않고 텍스트 파일에 타자할 수 있습니다. 데이터 구조는 그 이름만 타자하면 조사할 수 있습니다. 다음으로 또다른 파이썬 인터프리터 창으로 또는 또다른 파이썬 프로그램으로 잘라/붙일 수 있습니다. 구문 수정이 전혀 필요하지 않습니다.

보다 중요한 것은, 이 표현이 아주 확장성이 있다는 것입니다. 다른 알고리즘은 추가 속성을 이용하지만, 그 추가 속성들은 얼마든지 추가할 수 있습니다. 예를 들어, 단일-소스 최단 경로 알고리즘이나 너비-우선/깊이-우선 순회는 선행자 포인터 같은 추가 속성을 요구합니다. 파이썬에서 그 알고리즘은 그냥 선행자 속성을 (G.pred[v]와 같이) 그 그래프 객체에 추가하기만 하면 됩니다. 각 알고리즘에 대하여 하부클래스를 정의할 필요가 없습니다. 이렇게 새로 추가된 속성들도 새로운 루틴이 필요없이 직접 조사하고 수정할 수 있습니다.

6. 학생 평가

이 글을 쓰는 시점에서, 알고리즘 수업을 파이썬으로 두 번 제공했습니다. 전반적으로, 그 결과는 아주 긍정적입니다. 물론 여전히 개선의 여지는 있습니다. 이 섹션에서는 일화로 두 가지 측면을 다루어 보겠습니다.

성공적인 측면은 대부분의 학생들이 파이썬을 수용하는 분위기였다는 것입니다. 각 클래스 35-40여명의 학생 대부분은 성공적으로 프로그래밍 숙제를 큰 어려움 없이 완료할 수 있었습니다. 적어도 한 학생은 파이썬 광이 되었습니다. C++에서 파이썬으로 전환하여 이 강좌 이후로 자신의 연구 작업에 사용할 생각입니다. 현재 그는 Jython과 TkInter를 사용하여 사용자 인터페이스 위젯을 스크립트할 뿐만 아니라 파이썬으로 소켓 프로그래밍, 멀티스레딩, 그리고 고유의 C 코드를 스크립팅합니다. 더욱 고무적인 것은 프로그래밍 경험이 없는 여러 학생들이 학기말 쯤에는 파이썬을 상당히 잘 다루었다는 것입니다. 학생들은 에드몬드-카프(Edmonds-Karp)의 max-flow 알고리즘을 구현했고, 한 시간도 안되어 여러 예제들을 가지고 그 알고리즘을 검증했습니다. 이 알고리즘은 교과서에 제대로 설명되어 있지 않았습니다. 역시 프로그래밍 경험이 별로 없는, 또다른 학생은 주말 내내 같은 과제와 씨름을 했습니다. 그러나 교사의 힌트를 얻은 후에 결국 성공했습니다. 그 학생은 파이썬에서 복사와 매개변수 건넴의 의미구조가 어렵다고 푸념했지만, 정말 문제는 그가 E-K 알고리즘을 이해하지 못했다는 것이었습니다. 실제로 이해하자, 그것을 코딩하는 정말 정말 아주 쉬웠습니다. 대단히 고무적인 일은 상당한 학생들이 숙제로 내주지 않은 그 알고리즘을 구현하고 싶어했다는 것입니다. 학생들은 알고리즘이 실행되는 것을 보고 올바로 이해했는지 검증하고 싶다고 말했습니다. 이런 일화들은 모두 우리가 판단을 내리는데 기여했고 파이썬을 제일 처음 강좌에 사용해야 할 이유를 확신시켜 주었습니다.

그렇지만, 모든 학생들이 파이썬을 부드럽게 경험한 것은 아닙니다. 한가지 흔한 불평은 훌륭한 디버거가 없다는 것이었습니다. 저자는 학생들에게 작은 루틴을 짜보고 더 코드를 작성하기 전에 완전하게 테스트해 보라고 요구함으로써 응답했습니다. 방대한 프로그램을 짜놓고 첫 시도에 작동하리라고 기대하는 대신에 말입니다. 그렇지만, 모든 학생들이 수긍하지는 않았습니다. 리스트와 사전 그리고 객체 같은 복합 데이터 구조의 복사 의미구조도 약간 혼란을 야기했습니다. 그 설명을 읽기 숙제의 일부분에 포함시켜서 이 문제를 교정할 계획입니다. 어떤 경우에는 C++이나 Java에 경험이 많은 학생일 수록 파이썬에 적응하는데 더 어려움이 있었습니다. 어떤 학생은 느슨한 형정의라는 개념에 불편해 했습니다. 반면에 다른 학생들은 정점을 그냥 문자열로 생각하는 것을 어려워 했습니다. 문자열은 다양한 속성 사전에 해쉬 키로 사용이 가능합니다; 대신에, 그들은 정점을 객체로 생각하고 싶어했습니다. 몇몇 학생들은 그래프나 허프만 트리 데이터 구조에 대한 지시사항들을 따르지 않고, 많은 클래스와 하부클래스를 정의함으로써 파이썬 구문으로 Java나 C++ 스타일의 코드를 효과적으로 작성했습니다. 그런 프로그램 중 하나는 허프만 알고리즘에 대하여 길이가 12 페이지였습니다. 물론 대부분의 학생들은 대략 한 페이지에 그렇게 했습니다. 예상한 바와 같이, 코드의 12 페이지 대부분은 데이터 구조를 조작하고 포인터-연결 데이터 구조를 텍스트 형태로 예쁘게 인쇄하는 것에 소비되었습니다. 이것은 실제로는 파이썬의 문제가 아닙니다. 사실 그 때문에 파이썬을 일찍 교과과정에 도입하고자 하는 것입니다.

7. 맺는 말과 미래의 교육 계획

이 논고는 지난 이 년간 알고리즘 강죄에 파이썬을 사용했던 경험을 보고합니다. 알고리즘-지향적 언어로서, 파이썬은 학생들에게 알고리즘 디자인의 주요 개념들을 배울 수 있도록 해 줍니다. 전통적인 프로그래밍 언어의 낮은-수준의, 특이한 특징들과 싸우는 대신에 말입니다. 파이썬이 데이터 유형을 다루는 방식은 교과서가 알고리즘을 나타내는 방식과 완벽하게 일치합니다. 파이썬의 상호대화적 특성은 학생들이 그 언어로 실험을 하도록 장려합니다. 똑같이 중요한 것은 트리와 그래프에 대하여 우리가 새로운 방법으로 데이터 구조를 사용했다는 것입니다. 새로운 방법은 최대한 간결하면서도 사람이 읽을 수 있으며 파이썬 인터프리터에서 쉽게 받아들입니다. 프로그래밍 경험이 없는 졸업생도 수 많은 저-수준 프로그래밍 문제 때문에 좌절할 필요없이 교과서에서 의도한 수준에서 알고리즘을 실험할 수 있었습니다.

나는 파이썬을 수업에 채택했을 뿐만 아니라 연구 프로젝트에도 채택했습니다. 연구에서도 똑 같은 장점들을 누릴 수가 있기 때문입니다. 또한 현업에서 파이썬을 채택했다는 소식을 졸업생들로부터 들으면서 자신감이 생겼습니다. 현재 우리는 학부생의 프로그래밍 개론 시리즈를 개혁하여 파이썬을 주류로 포함시키려고 하고 있습니다. 이 글을 쓰는 시점에서, 이 학부는 2002년 가을 학기부터 첫 프로그래밍 개론 수업에서 C를 파이썬으로 교체해도 좋다고 대학의 승인을 받았습니다(ECE 12). 비-컴퓨터 공학 위원들로부터의 강력한 반대를 극복해야 합니다. 그 분들은 파이썬을 들어본 적이 없고 우리의 접근법을 의심합니다. 그들은 공학도들에게 프로그래밍을 "너무 부드럽게" 만든다고 비난합니다. "C가 문제 없는데 왜 고치려는겨?"라고 묻습니다. 우리는 그냥 프로그래밍이 아니라, 문제 해결 기술을 가르치고 싶습니다. C보다 파이썬이 훨씬 더 효과적으로 기본 개념들을 가르칠 수 있다는 확신이 있습니다. Jython과 TkInter를 통하여 CGI 꾸러미와 그래픽 꾸러미를 얻을 수 있다는 점도 C 또는 Java보다 학생 프로젝트에 대하여 더 매력적인 아이디어를 제공할 것입니다.

참조

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Second Edition, McGraw-Hill Press, September 2001. ISBN 0-262-03293-7.
2. Pai H. Chou, ECE 235 Website, University of California, Irvine, Fall 2000. http://e3.uci.edu/00f/15545/ See also Fall 2001 edition at http://e3.uci.edu/01f/15545/.
3. Algorithmic Solutions Software GmbH, homepage, http://www.algorithmic-solutions.com/, 2001.
4. Sara Baase, Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, Addison Wesley, 2000.
5. Mark Allen Weiss, Data Structures and Algorithm Analysis in JAVA, Addison-Wesley, 1999.

 

http://coreapython.hosting.paran.com/etc/Education%20with%20python.html 에서 퍼옴