요즘 철이 들었다는 핑계로, 강의를 찾아 듣고 있습니다. MOOC(Massive Open Online Courses)는 워낙 보편화되서 유명한 사이트들이 많습니다. 학술적인 느낌이 드는 곳은 Coursera, edx, Khan Academy 등이 있겠고, 실용적인 느낌이 드는 곳은 Udacity나 PluralSight가 있습니다. 그렇지만 다 영어라는 한계가 있습니다. 그래서 강의라고 해 봤자, 뭐 90%는 귓바퀴에 필터되기에 자막으로 띄엄띄엄 보는 수준입니다. Functional Programming in Scala라는 강좌인데, 이름에서 부터 알 수 있듯이 FP(Functional Programming)에 대해 잘 알 수 있을 것 같은 기분이 듭니다. Martin Odersky 교수가 진행하는데, 알다시피, Scala를 만든 사람입니다. 그런 사람의 직강이라니, 들으만 하겠죠? FP를 배우려는 목적이거나 Scala를 익히고 싶은 사람에게 도움이 될 것 같습니다. 이러한 강의는 특징은 주마다 진행되고, 과제도 있기에 동기 부여가 꽤 됩니다. 왠지 과제를 안내면 죄책감 같은 것도 들고, 과제를 제출하고 만점을 받으면 조금 우쭐한 기분이 들기도 합니다.

강의는 이제 3주차라, 소개 글이 빈약할 수 밖에 없습니다만... 마법사의 책이라 불리는 SICP(Structure and Interpreation of Computer Programming)라는 책을 바탕으로 진행합니다. SICP는 개발자라면 책꽂이에 있으며, 읽지는 않았으나 곧 읽을 예정으로 손 꼽히는 책입니다. 만약에 이 책을 보셨다면, 마치 SICP의 Scala 버전이라는 느낌을 드실 수 있습니다. 물론, 이후의 강의가 어떻게 진행될지는 모르겠지만, 현재까지는 비슷한 맥락으로 진행되고 있습니다.

사실, 오늘 포스팅을 한 건, 강의 중에 놓친(사실은 풀지 못한) 문제 때문입니다. '어렵다'의 정의가 '내가 생각해 낼 수 없었다'라고 한다면, 이 문제는 분명 어려운 문제입니다. 해답을 제시하는 것은 스포이기에, 여기서는 문제의 소개와 제가 느꼈던 소회만 남기도록 하겠습니다. 답이 궁금하시거나 조금 더 깊이 이해하고 싶다면, 위의 강의를 추천드립니다.

동전 수 세기

첫 째주의, 과제로 나온 문제입니다. 문제는 지극히 간단합니다. 만약에 4원을 내야 하고, 동전이 1원과 2원이 있다고 하면, 몇 가지 경우의 수로 4원을 낼 수 있을까?

예를 들면,
4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 2 + 2

이렇게 3가지 경우가 있겠습니다. 참, 간단하죠.

def calculateCoins(money: Int, coins: List[Int]): Int = ???

// test cases
assert(calculateCoins(4, List(1,2)) == 3)
assert(calculateCoins(300, List(5, 10, 20, 50, 100, 200, 500)) == 1022)

scala 문법으로 작성된 코드입니다만, 뭐 언어는 상관없습니다. calculateCoins()를 구현하시면 됩니다. 언어가 어색해? 그럼 다음과 같이 표현할 수도 있겠죠.

// C#
int calculateCoins(int money, List[int] coins) {
    // ...
}


// JavaScript
function calculateCoins(money, coinArray) {
    // ...
}

어떤 언어로든, 300원을 지급할 때에는 5, 10, 20, 50, 100, 200, 500의 동전으로 1022개의 경우의 수를 구해낼 수 있으면 됩니다.

참고로, 부끄러운 이야기지만 전 풀지 못했습니다. 하지만 여러분은 풀 수 있을거라 생각합니다. :)

집합의 union 구현하기

이건, 3주차에 수업 시간에 나온 문제인데, 조금 접근이 신박했습니다. 마치, 점화식을 정의하듯 문제를 정의하는게 신기했습니다. 비슷하게는, Haskell에서 함수를 정의하는 방식과 비슷하다고 애기하는게 맞는 표현일 듯 합니다. 일단, Set(집합)이 있습니다. Set을 직접적으로 정의하는게 아니라, 다음처럼 Interger Set에 대한 추상 클래스를 만듭니다.

abstract class IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
  def union(other:IntSet):IntSet
}

Scala 문법이지만, 대충 이해하셨을 거라 생각합니다. 함수는 def로 정의하고 콜론을 이용해서 함수의 반환 타입을 설정합니다. incl()은 Int를 받아서, Set을 반환하는 함수가 되겠습니다. 즉, 새로운 Set을 만드는 함수입니다. contains()는 Set에 특정 숫자가 포함되었는지를 체크하는 함수 입니다. union()은 아시다시피, 두 개의 Set을 합치는 함수입니다.

Set은 다음과 같이 정의 됩니다. 먼저 정의하는 것은 빈 집합(EmptySet)입니다.

object Empty extends IntSet {
  def contains(x: Int):Boolean = false
  def incl(x:Int):IntSet = new NonEmpty(x, Empty, Empty)
  def union(other:IntSet):IntSet = other
}

빈집합이 있다고 생각합시다. 그 EmptySet에 contains()로 포함 여부를 물으면 언제나 false가 나올 수 밖에 없을 것 입니다. incl()을 집합에 원소를 추가하는 함수라고 말씀드렸습니다. 자기 자신은 빈 상태이므로, 이후의 정의할 NonEmptySet을 호출하게 됩니다. 그리고 빈 집합과 union()을 하게 되면, 당연히 주어진 집합이 나오겠죠. 아주 간결하고 깔끔해서 오류의 소지가 없어 보입니다.

이제는 NonEmpty를 정의해 보겠습니다.

class NonEmpty(elem:Int, left:IntSet, right:IntSet) extends IntSet {
  def contains(x: Int):Boolean =
    if (elem > x) right.contains(x)
    else if(elem < x) left.contains(x)
    else true

  def incl(x:Int):IntSet =
    if (elem > x) new NonEmpty(elem, left incl x, right)
    else if (elem < x) new NonEmpty(elem, left , right incl x)
    else this

  def union(other:IntSet):IntSet = ???
}

NonEmpty는 3개의 인자를 받습니다. Set의 원소로서 어떤 숫자를 가르키는지, 그리고 좌측 집합과 우측 집합을 받게 됩니다. 즉, 위의 구조는 Set의 각 인자를 Binary Tree로 구성하고 있는 셈입니다. incl()와 contains()에서 보시다시피, 좌측에는 주어진 숫자 보다 작은 수의 집합이 와야 하며 우측에는 더 큰 수의 집합이 와야 함을 알 수 있습니다. 이러한 가운데, union()을 작성하는 것이 문제입니다. 앞의 규칙을 만족시키는 union() 어떻게 작성할 수 있을까요?

사실, 이 문제도 저는 어려웠습니다. 2개의 Set을 합친다는 것이, 주어진 IntSet Class로 어떻게 이뤄질지 전혀 감을 잡을 수 없었습니다. Set을 전체를 다 새로 통합해서 만들어야 하는 건지, 그렇다면 other의 elem에 대한 접근은 어떻게 할지... 저는 이런저런 고민이 많았지만, 여러분들은 더욱 쉽게 풀 수 있을거라 생각합니다.

Closing

앞으로, Functional Programming in Scala에 대한 포스팅이 1~2차례 더 있을 것 입니다. 마치고나면, 기분 좋아서 하나 더 끄적이겠죠. 오늘의 포스팅은 여러분에게 좋은 문제를 소개하는 것 처럼 적었습니다만, 사실 head fake입니다. 이건, 제가 이런 간단한 문제도 풀지 못했기에, 잊지 않고자 한번 더 정리한 글이었습니다. 그러한 가운데, 여러분에게도 도움이 되셨다면 좋겠습니다.