[8/20] 사례 연구: 워드 플레이

글을 시작하기에 앞서 해당 시리즈는 Allen Downey, Ben Lauwens의 저서인 Think Julia: How to Think Like a Computer Scientist 를 바탕으로 작성된 글임을 알려드립니다.

이 포스트는 Case Study: Word Play를 한글로 요약 정리한 글입니다.

사례 연구: 워드 플레이 (Case Study: Word Play)

이번 장에서는 특정 속성을 가진 단어를 검색하여 단어 퍼즐을 해결하는 사례 연구를 할 것이다. 예를 들어, 영어로 된 가장 긴 회문(palindrome)을 찾아 알파벳순으로 글자가 나타나는 단어를 검색하는 것이다. 그리고 위의 방식을 축소할 수 있는 다른 프로그램들도 제시할 것이다.

단어 리스트 불러오기

위의 연구를 시작하기에 앞서 우리는 단어 리스트들이 필요하다. 웹에는 많은 단어 리스트들이 있지만, 우리는 그 중 Moby lexicon project에서 사용된 단어 리스트인 Grady Ward를 사용할 것이다. 이 리스트에는 총 113809개의 단어가 저장되어 있으며, 우리는 이 단어들을 전부 사용할 수 있다. 파일의 이름은 113809.of.fic이며, 다운로드는 이 링크에서 할 수 있다.

줄리아로 텍스트 파일을 여는 방법은 다음과 같다. 우선 내장 함수인 open()에 인수로 텍스트 파일 이름을 넣어서 파일을 가져올 것이다.

julia> fin = open("words.txt")
IOStream(<file words.txt>)

Tip 만약 위의 코드 실행 시 오류가 발생한다면, 대부분은 디렉토리 설정 오류일 것이다. 해결 방법은 아래와 같다.

julia> pwd() # 현재 디렉토리 확인
julia> cd ($(pwd())/단어 리스트 파일 위치)
julia> pwd() # 다시 확인

fin은 입력에 사용되는 파일 스트림이며, 더 이상 필요하지 않은 경우에는 close(fin)으로 닫아야 한다.

줄리아는 readline()을 포함하여 몇 가지의 읽기 함수를 제공한다. readline()은 NEWLINE에 도달할 때까지 파일에서 문자를 읽고 결과를 문자열로 반환한다.

julia> readline(fin)
"aa"

가져온 단어 리스트 중에 첫 번째 단어는 "aa"이며, 용암의 이름이다. 파일 스트림은 파일에서의 위치와 경로를 파악하고 있기 때문에 readline()을 한번 더 호출하면 다음 단어를 반환한다.

julia> readline(fin)
"aah"

다음 단어는 "aah"이다. 좀 이상하지만 실제 있는 단어이다.

또한 for루프를 사용하여 파일 내부의 단어들을 모두 가져올 수 있다. 아래의 프로그램은 words.txt를 읽고 한 줄에 한 단어씩 출력한다.

for line in eachline("words.txt")
    println(line)
end

검색 (Search)

검색 패턴으로 해결할 수 있는 가장 간단한 예는 다음과 같다.

function hasno_e(word)
    for letter in word
        if letter == 'e'
            return false
        end
    end
    true
end

for루프는 단어의 알파벳들을 순회한다. 알파벳 e를 찾으면 즉시 거짓을 반환하며, 그렇지 않다면 다음 알파벳으로 이동한다. 만약 단어에서 e를 못찾았다면 true를 반환하고 종료한다.

∉(\notin TAB) 연산자를 사용하여 위의 코드를 더 간결하게 작성할 수 있다. 다만 위의 함수는 검색 패턴이 어떻게 작동하는지 확인하기 위해서 먼저 살펴본 것이다.

avoids()는 hasno_e()를 일반화시킨 함수이며, 안의 구조는 똑같다.

function avoids(word, forbidden)
    for letter in word
        if letter ∈ forbidden
            return false
        end
    end
    true
end

두 번째 인수인 forbidden이 word에 속해 있다면 false를 반환하며, 루프가 끝까지 진행되면 true가 반환된다.

usesonly()는 avoids()과 조건만 반대이고 나머지 구조는 같다.

function usesonly(word, available)
    for letter in word
        if letter ∉ available
            return false
        end
    end
    true
end

usesonly()는 forbidden 문자 배열 대신에 available 문자 배열이 들어가며, word 알파벳 중에서 available에 속한 문자가 없다면 false를 반환한다.

또한 포함되어야 하는 알파벳 문자열을 사용한 usesall()은 아래와 같다.

function usesall(word, required)
    for letter in required
        if letter ∉ word
            return false
        end
    end
    true
end

usesall()은 루프에서 word의 알파벳을 가져오는 것이 아니라 required에서 알파벳을 가져온다. 만약 required 알파벳이 word에 없다면 false를 반환한다.

만약 실제 컴퓨터 과학자처럼 생각한다면, usesall()이 usesonly()와 인수 위치만 변화된 것을 파악할 수 있다.

function usesall(word, required)
    usesonly(required, word)
end

위의 코드는 이전에 만들었던 함수로 프로그램 개발을 축소하는 과정의 예이다. 인자 설정만 잘하면 기존 함수들을 이용하여 문제를 해결할 수 있다.

인덱스를 이용한 루핑

그동안은 문자열 안에 문자만 필요했기 때문에 for 루프를 사용해서 함수를 작성해왔다. 즉, 인덱스를 사용할 필요가 없었다.

하지만 아래의 isabecedarian()는 단어 안의 특정 문자와 인접한 문자들을 비교해야 하기 때문에 for 루프를 사용하면 함수 작성이 어려워진다. 참고로 isabecedarian()는 알파벳 순서로 작성된 단어인지를 판단하는 함수이다.

function isabecedarian(word)
    i = firstindex(word)
    previous = word[i]
    j = nextind(word, i)
    for c in word[j:end]
        if c < previous
            return false
        end
        previous = c
    end
    true
end

재귀를 사용한 대안은 아래와 같다.

function isabecedarian(word)
    if length(word) <= 1
        return true
    end
    i = firstindex(word)
    j = nextind(word, i)
    if word[i] > word[j]
        return false
    end
    isabecedarian(word[j:end])
end

while 루프를 사용한 다른 방법은 아래와 같다.

function isabecedarian(word)
    i = firstindex(word)
    j = nextind(word, 1)
    while j <= sizeof(word)
        if word[j] < word[i]
            return false
        end
        i = j
        j = nextind(word, i)
    end
    true
end

위의 코드에서 루프는 i=1 와 j=nextind(word, 1)로 시작하며, j>sizeof(word)일 때 끝난다. 각각의 루프는 i(현재 알파벳)와 j(다음 순서의 알파벳)를 비교한다.

만약 j보다 i가 더 크면, 알파벳의 순서가 깨졌기 때문에 false를 반환한다. 그 외에 while 루프가 다 끝나면 그 단어는 해당 테스트를 통과한 것이다. 루프가 잘 작동하는지 확인하기 위해서 예시인 "flossy"를 넣어서 실행해보자.

아래의 코드는 문자열의 처음과 끝을 인덱스로 잡아 비교하는 함수 ispalindrome()이다.

function ispalindrome(word)
    i = firstindex(word)
    j = lastindex(word)
    while i<j
        if word[i] != word[j]
            return false
        end
        i = nextind(word, i)
        j = prevind(word, j)
    end
    true
end

또한 우리가 함수를 이용해서 더 간결하게 작성할 수 있다.

function ispalindrome(word)
    isreverse(word, word)
end

디버깅

프로그램을 테스트하는 것은 어렵다. 이 장에서 작성한 함수들은 작성자가 직접 결과를 확인할 수 있기 때문에 테스트하기 쉽게 연결된 형태이다. 그렇지만 오류 가능성을 확인하기 위한 단어를 선택하는 것은 어렵고 거의 불가능하다.

hasno_e를 예시로 보면, 이 함수에는 명백하게 확인해야 할 것들이 두 가지가 있다. e 가 들어간 단어는 무조건 false를 반환해야 하며, true를 반환해서는 안된다. 아마 단어 각각을 대입했을 때에는 문제가 없었을 것이다.

각 e를 포함하고 있는 단어들은 e의 위치를 파악하기 위해서 시작점, 끝, 그리고 중간쯤에도 확인을 해야한다. 그렇기 때문에 긴 단어, 짧은 단어, 빈 문자 등을 테스트해야 한다. 빈 문자(empty string)는 에러가 어디있는지 숨겨주기 때문에 명확하지 못한 조금 특별한 경우이다.

게다가 일반화하기 위해 실행하는 테스트의 경우, 단어 리스트 전체를 사용해서 프로그램을 테스트해야 한다. 결괏값을 출력함으로써 오류들을 확인할 수 있다. 주의해야 할 점은 실제로 오류가 없지만 오류로 파악되는 경우, 실제로 오류가 있지만 보이지 않는 경우 등이 있을 수 있다.

일반적으로 테스트하는 것은 버그를 찾는 데 도움을 주지만, 몇몇의 좋은 테스트 결과만을 가지고 코드를 일반화하기는 어렵다. 심지어 테스트를 많이 해도 프로그램이 올바르게 작동되고 있다고 확신하기는 어려울 것이다.

전설적인 컴퓨터 사이언티스트는 아래와 같이 말했다.

"프로그램 테스팅은 버그를 미리 보기 위해 사용되지만, 버그가 없다는 결론을 보여주지는 않는다."