TDD 로 알고리즘 풀이

TDD

테스트 주도 개발 (Test Driven Development) 로 기능에 대한 테스트를 먼져 작성한 뒤 테스트가 통과할 수 있는 코드를 작성하는 것을 뜻한다. 예전에는 이러한 방법이 단순히 더 느리다고만 생각했는데, 요즘 드는 생각은 TDD 로 하는 방법이 일반 방법보다 때로는 빠를때도 많다는 것이 내 의견이다.

사람들이 TDD 책을 읽지 않고 단순히 테스트 먼져 적으면 되는거 아니야? 라고 해서 TDD 를 시작하게 되면 당연하게도 TDD 가 느리네 라고 생각할 수 밖에 없다. 그래서 켄트백과 최범균님의 책을 읽고나서 내가 느낀 경험을 바탕으로 TDD 를 하는 방법을 적어보려고 한다.

Know-how

일단 켄트백의 TDD 책을 읽어보면 테스트를 쉽게 할 수 있는 작은 기능을 찾는게 가장 중요하다. 이게 가장 중요한데 작은 기능 -> 큰 기능으로 점진적으로 발전 시켜나가는 식으로 문제에 접근하다보면, 오히려 큰 기능 -> 작은 기능 으로 내려오는 것보다 내 경우에서는 빠르게 문제가 해결되었다.

일단 백문이 불여일타라고 실제로 알고리즘 문제를 풀면서 내가 어떻게 TDD 를 하는지 간단하게 시연해보려고 한다.

문제 풀이

문제는 Leetcode 에서 Generate Parentheses 라는 문제를 선택했다.
난이도는 medium 급이고, 문제 내용은 아래와 같다.

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

해석하자면, N 개의 쌍의 괄호가 주어졌을때 괄호가 제대로 완성될 수 있는 모든 조합을 생성하는 함수를 작성해라. 이다. 이제 한번 TDD 로 문제를 풀어보자.

주어진 TEST CASE 는 일단 아래와 같다.

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

이 문제를 풀기 위한 가장 작은 기능을 찾아야 한다. 일단 무작정 코드를 적기보다, 내가 완성시켜야 하는 기능이 뭘까를 먼져 생각해보자. 일단 내 기준에서 떠오르는 필요한 기능은 아래와 같다.

1. 괄호가 정상적으로 놓인 것인지 확인할 수 있는 Function
2. N 개의 쌍의 well-formed 형태의 괄호의 모든 조합(앞자리가 무조건 '(' 으로 시작하는)을 만들 수 있는 Recursive Function (1번 Function 이용)

일단 위의 기능만 있다면 문제는 해결 가능하다고 생각했다. 그렇다면 괄호가 정상적으로 놓였는지 확인할 수 있는 Function 의 테스트 부터 만들어보자.

class Question22 : BehaviorSpec({  

    val validator = Validator()  

    given("given Input parentheses = '((()))'") {  
        val parentheses = "((()))"  
        `when`("execute isWellFormedParentheses Method") {  
            val result = validator.isWellFormedParentheses(parentheses = parentheses)  
            then("then return true") {  
                result shouldBe true  
            }  
        }            
    }
})

위의 테스트는 Validator 를 통해서 주어진 parentheses 가 정상적인 괄호 폼인지 확인하는 테스트이다. 일단 테스트 먼져 작성했기 때문에 Validator 클래스와 isWellFormedParentheses 메소드가 없어서 컴파일 조차 되지 않게 된다. TDD 원칙에 맞게 가장 빠르게 성공할 수 있게 코드를 완성시켜보자.

class Validator {  
    fun isWellFormedParentheses(parentheses: String): Boolean {  
        return true  
    }  
}

위와 같이 코드를 작성하고 테스트를 돌려보면, 아주 잘 통과하는 모습을 확인할 수 있다.

그렇다면 실패하는 테스트도 하나 만들어보자. ()) 의 경우에는 false 가 나와야 정상일 것 이다.

given("given Input parentheses = '())'") {  
    val parentheses = "())"  
    `when`("execute isWellFormedParentheses Method") {  
        val result = validator.isWellFormedParentheses(parentheses = parentheses)  
        then("then return false") {  
            result shouldBe false  
        }  
    }
}

테스트 메소드는 위와 같은 형태일 것이고, false 가 정상적으로 나와야 하는 케이스이다. 한번 테스트를 돌려보자.
아래 사진을 보면 테스트가 실패하고 있음을 알 수 있다.

그렇다면 이제 어떻게 괄호가 정상적인지 검증할 수 있는지 생각해보자. 가장 쉬운 방법으로는 ( 은 +1 , ) 은 -1 을 해주면서 최종적으로 0이 되는지를 검증하고, 중간에 0보다 작아진다면 false 를 return 하게 하는 것이다. 코드를 적으면 아래와 같은 코드가 나오게 된다.

class Validator {  
    fun isWellFormedParentheses(parentheses: String): Boolean {  
        var count: Int = 0  
        for (c in parentheses) {  
            if (count < 0) return false  
            if (c == '(') count++  
            if (c == ')') count--  
        }  
        return count == 0  
    }  
}

이제 테스트를 한번 돌려보자.

정상적으로 잘 통과된다. 첫번째 기능을 완성되었다. 이제 두번째 기능을 생각해보자.

두번째 기능

이제 두번째 기능인 "N 개의 쌍의 well-formed 형태의 괄호의 모든 조합(앞자리가 무조건 '(' 으로 시작하는)을 만들 수 있는 Recursive Function" 을 생각해보자. 여기서 부터는 크게 N 을 3이라고 생각하게 되면 설계하기 힘드므로, 제일 쉽게 통과시킬 수 있는 1 일때 () 이 나온다 부터 시작해보자. 테스트 코드를 작성해보면 아래와 같을 것이다.

given("given Input n = 1") {  
    val n = 1  
    `when`("execute generateParentheses Method") {  
        val result = parenthesesGenerator.generate(pair = n)  
        then("then return ['()']") {  
            result shouldBe listOf("()")  
        }  
    }
}

테스트 코드를 빠르게 통과시키기 위해서 또 코드를 작헝해보자.

class ParenthesesGenerator {  
    fun generate(pair: Int): List<String> {  
        return listOf("()") 
    }  
}

테스트를 통과시키기 위해서 위와 같이 코드를 작성할 수 있을 것 이다. 이제 테스트를 한번 돌려보자.

테스트가 정상적으로 통과하는 모습을 볼 수 있다. 이제 한번 2를 넣어보자. 2를 넣었을때는 어떤 경우의 가짓수가 나올 수 있을까? 일단 4개의 괄호가 사용될 것이다. 따라서 4개의 괄호중 정상적인 형태는 아래 두가지 케이스 일 것이다. ['(())', '()()'] 일단 테스트 케이스 부터 만들어보자.

given("given Input n = 2") {  
    val n = 2  
    `when`("execute generateParentheses Method") {  
        val result = parenthesesGenerator.generate(pair = n)  
            then("then return ['(())', '()()']") {  
            result shouldBe listOf("(())", "()()")  
        }  
    }
}

해당 테스트 코드를 실행해보면 실패함을 확인할 수 있다. 그렇다면 우리는 이제 우리가 위에서 언급한 N 개의 쌍의 괄호의 조합을 완성시키는 코드를 적어야 한다. 첫번째는 반드시 '(' 으로 시작하고, 그 이후에 '(', ')' 을 붙여 나가면 되므로, 이는 재귀로 작성하기 쉬운 코드이다. N 개의 쌍은 곧 Depth 가 된다.

Recursive 하게 이용하기 위해서는 Depth 를 Argument 로 전달해줄 필요가 있다. 재귀 형태의 메소드를 하나 만들어보자.

class ParenthesesGenerator {  

    val validator = Validator()  

    fun generate(pair: Int): MutableList<String> {  
        val parentheses = mutableListOf<String>()  
        val startWord = "("  

        xx(pair = (pair * 2 - 1), depth = 0, word = startWord, parentheses = parentheses)  

        return parentheses  
    }  

    fun xx(pair:Int, depth: Int, word: String = "(", parentheses: MutableList<String>) {  
        if (depth == pair) {  
            if (validator.isWellFormedParentheses(word)) parentheses.add(word)  
            return  
        } else {  
            xx(pair, depth + 1, "$word(", parentheses)  
            xx(pair, depth + 1, "$word)", parentheses)  
        }  
    }  
}

위에서 설명한 것과 같이 계속해서 '(', ')' 을 붙여나가고, 우리가 첫번째로 검증했던 1번 Function 을 이용해 Well-Formed 일 경우에만 List 에 추가하도록 변경했다. 한번 테스트를 돌려보자.

잘 통과하는 모습을 확인할 수 있다. 그리고 LeetCode 에 주어져있는 3개일때의 TESTCASE 를 이용해서 테스트 코드를 하나 더 작성해보자.

given("given Input n = 3") {  
    val n = 3  
    `when`("execute generateParentheses Method") {  
        val result = parenthesesGenerator.generate(pair = n)  
        then("then return ['((()))','(()())','(())()','()(())','()()()']") {  
            result shouldBe listOf("((()))","(()())","(())()","()(())","()()()")  
        }  
    }
}

잘 통과하는 모습을 확인할 수 있다. 이제 우리는 작은 기능 두가지를 완성했다. 이제 무엇을 해야할까? 바로 Refactoring 이다. 위의 코드를 보면 xx() 를 사용하거나, 접근제한자에 대한 부분이 전혀 신경써져있지 않다. 과감하게 리팩토링을 진행하자.

일단 xx() 의 이름을 괄호를 붙여준다는 뜻으로 appendParentheses 로 바꿨다.

class ParenthesesGenerator {  

    val validator = Validator()  

    fun generate(pair: Int): MutableList<String> {  
        val parentheses = mutableListOf<String>()  
        val startWord = "("  

        appendParentheses(pair = (pair * 2 - 1), depth = 0, word = startWord, parentheses = parentheses)  

        return parentheses  
    }  

    private fun appendParentheses(pair:Int, depth: Int, word: String = "(", parentheses: MutableList<String>) {  
        if (depth == pair) {  
            if (validator.isWellFormedParentheses(word)) parentheses.add(word)  
            return  
        } else {  
            appendParentheses(pair, depth + 1, "$word(", parentheses)  
            appendParentheses(pair, depth + 1, "$word)", parentheses)  
        }  
    }  
}

리팩토링 했으니, 이제 테스트 코드를 돌려보자.

전부다 통과함을 확인할 수 있다. 이제 validator 를 살펴보자. 사실 validator 는 굳이 외부로 노출될 필요가 없는 property 이다. 이를 private 으로 만들자.

class ParenthesesGenerator {  

    private val validator = Validator()  

    fun generate(pair: Int): MutableList<String> {  
        val parentheses = mutableListOf<String>()  
        val startWord = "("  

        appendParentheses(pair = (pair * 2 - 1), depth = 0, word = startWord, parentheses = parentheses)  

        return parentheses  
    }  

    private fun appendParentheses(pair:Int, depth: Int, word: String = "(", parentheses: MutableList<String>) {  
        if (depth == pair) {  
            if (validator.isWellFormedParentheses(word)) parentheses.add(word)  
            return  
        } else {  
            appendParentheses(pair, depth + 1, "$word(", parentheses)  
            appendParentheses(pair, depth + 1, "$word)", parentheses)  
        }  
    }  
}

다시 테스트 코드를 돌려보자.

잘 통과함을 확인할 수 있다. TDD 는 위와 같은 프로세스로 진행된다. 테스트 코드 작성 -> 테스트를 통과하는 실제 구현체 작성 -> 테스트 확인 -> 리팩토링 -> 테스트 확인 이와 같은 형태의 계속되는 반복으로, 리팩토링할때 개발자에게 좀 더 자신감을 더해주게 된다.

최종

이제 메소드를 조합하여서 Leetcode 에 제출해야 하므로, Leetcode 형태로 테스트 코드를 작성하자

given("[Final] given Input n = 3") {  
    val solution = Solution22()  
    val n = 3  
    `when`("execute generateParenthesis Method") {  
        val result = solution.generateParenthesis(n)  
        then("then return ['((()))','(()())','(())()','()(())','()()()']") {  
            result shouldBe listOf("((()))","(()())","(())()","()(())","()()()")  
        }  
    }
}

우리는 작은 기능들을 통해 이미 동작함을 증명했으므로 완성되는 코드는 아래와 같다.

class Solution22 {  
    val parenthesesGenerator = ParenthesesGenerator()  

    fun generateParenthesis(n: Int): List<String> {  
         return parenthesesGenerator.generate(pair = n)  
    }  
}

한번 제출해보자.

잘 풀렸음을 확인할 수 있다. 시간 복잡도 측면에서 어떻게 효율화 할 수 있을지는 문제를 풀고, 자신이 생각해보아도 좋다. 일단 우리에게는 작성한 테스트가 있으므로 자신이 리팩토링을 쉽게 할 수 있을 것이다.

후기

알고리즘을 풀때 TDD 로 풀면 정말 빠르다. 다만 2번 힘수의 경우 내 기준에서는 작은 기능에 해당한다고 생각했는데, 글을 적고 다시 읽어봤을때는 모든 조합을 만드는 경우 그리고 모든 조합에서 1번 함수를 이용하여 발라내는 경우로 더 잘게 쪼갰어야 되는데 라는 생각이 많이 들었다. 여하튼, 켄트백도 말하듯이 작은 단위를 찾는게 실력이므로 계속해서 해당 Function 을 완성하는데, 테스트를 통과시킬 수 있는 가장 작은 단위 테스트를 찾아내는걸 계속 연습해야 한다는 사실을 잊지 말아야 한다.

번외) Leetcode 는 내 방식대로 푸는게 지금은 주먹구구식으로 거의 푼것이므로, Discuss 의 Best Solution 을 한번 보고 다른 사람은 어떻게 풀이하는지 한번 보는게 좋다.

Github

https://github.com/tmdgusya/kotlin-leetcode/blob/master/src/test/kotlin/Question22.kt

GitHub - tmdgusya/kotlin-leetcode

공부할때 읽으면 좋은 책

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9788966261024 

테스트 주도 개발 - 교보문고

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9788980783052&orderClick=LEa&Kc= 

테스트 주도 개발 시작하기 - 교보문고