저는 개발 멘토링 플랫폼 F-Lab에서 Young이라는 닉네임으로 멘토링을 하고 있습니다. 아래 글은 F-Lab 블로그에 기고한 글을 바탕으로 작성했습니다. 원본은 여기서 볼 수 있습니다.

저는 멘티들이 코딩을 많이 하기를 바라는데요. 그 일환으로 쉬운 난이도의 알고리즘 문제를 많이 풀도록 시키고 있습니다.

사실 실무에서 고난이도의 알고리즘 문제를 풀어야하는 경우는 거의 없습니다. 직무에 따라 다르긴 하지만, 대부분의 프로그래머는 programmers 기준 레벨 2 이하의 문제를 반복해서 풀며 일합니다. 물론 실무에서 마주치는 문제가 알고리즘만 있는게 아니기에, 일의 전체적인 수준이 레벨 2 이하란 얘기는 아닙니다.

레벨 3 이상의 문제는 열쇠 구멍이 딱 하나 있는 상자라고 볼 수 있습니다. 문제에 숨겨진 한 두개의 흥미로운 성질이 있고, 그걸 발견하면 풀 수 있고 못 발견하면 못 풀도록 설계되어 있습니다. 여러 풀이들 간에는 약간의 스타일 차이만 있을뿐 그 논리는 동일합니다.

반면 레벨 2 이하의 문제들은 여러 종류의 풀이에 너그럽습니다. 특별히 기발한 발상이 필요없는 경우도 많고요. 그런 여유가 생긴 덕택에, 어떻게 하면 잘 풀까에 집중할 수 있습니다. 그리고 얼마나 잘 푸느냐가 실무에서 아주 중요하다고 저는 생각합니다.

예시를 들어 설명해볼게요.

예시 문제: Roman To Int

멘티 분이 풀어온 문제 중에 leetcode의 Roman To Int라는 문제가 있었습니다. 로마 숫자를 읽어서 우리에게 익숙한 십진법으로 출력하는 문제인데요.

로마 숫자 읽는 방법을 대강은 알고 계실겁니다. I는 1, X는 10, C는 100에 대응되는 방식의 규칙이 있고, 대응시킨 다음에 다 더하면 됩니다. 가령 CXXIII는 123이고, DILIVI는 666입니다.

여기까진 보면 너무 쉽죠? 예외 사항이 있는데, IX는 11이 아니고 9입니다. XI는 10 + 1 = 11이지만 순서가 바뀌면 10 - 1 = 9가 됩니다.

멘티의 풀이는 다음과 같았습니다. 좀더 간결하게 고쳤지만 논리는 그대로입니다.

def romanToInt(s: str) -> int:
    dictionary={
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

    n = 0
    xs = [dictionary[i] for i in s]
    for i, x in enumerate(xs[:-1]):
        if x < xs[i+1]:
            n -= x
        else:
            n += x
    n += xs[-1]

    return n

잘 풀었습니다. 코딩 테스트를 보는데 저 풀이가 떠오르면 그냥 저렇게 풀면됩니다.

하지만 사소한 문제가 하나 있습니다. 제가 보기엔 풀이가 너무 똑똑합니다. 제가 코딩 테스트에서 같은 문제를 마주치면 바로 저 풀이를 떠올리지 못할 거 같습니다.
대신 좀더 멍청한 방법으로 풀 거 같네요. 제 풀이는 이렇게 시작합니다.

def romanToInt(s: str) -> int:
    dictionary = {
        'IX': 9,
        'IV': 4,
        'XL': 40,
        'XC': 90,
        'CD': 400,
        'CM': 900,
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

나머지 부분을 어떻게 완성해야하는지 보이시나요? 제가 처음에 멘티에게 저 코드를 완성하라고 시켰을때, 하루가 지나고도 완성을 해오지 못했습니다. 굉장히 의외였습니다. 나중에 다른 멘티도 첫번째 방법으로 풀길래 같은 숙제를 내주었습니다. 그 분도 하루종일 고민하고 풀지 못했습니다.

이상하죠. 왜 더 똑똑한 풀이를 떠올려놓고, 더 멍청한 풀이는 생각해내지 못하는 걸까요? 저는 이 사실을 관찰하고나서 이후의 멘토링 방향에 대해 많은 생각을 했었습니다.

일단 저의 멍청한 풀이를 마저 보시죠. 논리를 명확히 보여주기위해 일부러 더 풀어서 썼습니다.

def romanToInt(s: str) -> int:
    dictionary = {
        'IX': 9,
        'IV': 4,
        'XL': 40,
        'XC': 90,
        'CD': 400,
        'CM': 900,
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

    def find_prefix(s):
        for k in dictionary.keys():
            if s.startswith(k):
                return k
        raise

    tokens = []
    while s:
        prefix = find_prefix(s)
        tokens.append(prefix)
        s = s[len(prefix):]
        
    return sum(dictionary[i] for i in tokens)

이 풀이가 앞의 똑똑한 풀이에 비해 더 나은 점이 있다고 한다면, 그게 뭘까요? 잠깐 생각해보는 시간을 갖기를 권장합니다. 그리고 지금부터 똑똑한 풀이를 풀이A, 멍청한 풀이를 풀이B라고 부르겠습니다.

똑똑한 풀이 vs 멍청한 풀이

풀이A는 간결하고 풀이B는 구구절절합니다. 또 풀이A는 재치있는데 반해, 풀이B는 심심합니다. 어, 그러면 풀이A가 더 좋은거 아닌가요? 풀이B에는 대신 아주 실용적인 장점이 있습니다.

풀이B는 확장과 변경이 쉽습니다.

가령 Chinese To Int라는 짝퉁 문제가 나오더라도, dictionary를 수정하는 것만으로 대응가능합니다. 이는 문제를 큰 덩어리로 나눠서 풀었기 때문에 가능합니다. 문자열을 읽는 부분, 즉 문자열을 의미를 가진 부분 문자열로 나누는 부분과, 나뉜 문자열로 합산하는 과정을 나뉘어져 있습니다. 그리고 그 합산에 필요한 규칙, 로마자와 숫자의 대응도 dictionary 변수로 나누어져 있습니다. 그래서 문제가 부분적으로 바뀌었을때, 풀이도 거기 대응하는 부분만 바꾸면 됩니다.

여기엔 이런 반론이 가능하겠죠. 알고리즘 문제에 확장과 변경을 고려하는게 과연 의미가 있는가?

풀이A든 풀이B든, 한번 풀고나선 다시 안 볼 코드란걸 생각하면, 맞습니다. 하지만 확장과 변경은 문제를 푸는 도중에도 일어납니다.

가령, 풀이A를 제출했는데 답안이 몇개 틀렸다고 나오는 경우를 상상해봅시다. 문제를 다시 읽어봤더니 잘못된 로마 숫자에 대해서는 -1을 출력하라는 조건이 있었습니다. 실제로 leetcode의 문제엔 그런 조건이 없습니다. 하지만 이 조건을 추가하는게 난이도를 크게 올린다고 생각하진 않을 겁니다.

풀이A에 IC가 입력으로 주어지면 99가 나올 겁니다. 하지만 저건 잘못된 로마 숫자입니다. I는 C앞에 나오면 안됩니다. 이런 사소한 예외사항은 늦게 발견하더라도 ‘아하, 별거 아니었네’하고 고쳐서 제출할수 있어야야겠죠? 하지만 풀이A는 조금만 고쳐서 통과하지 못합니다. 고치다보면 풀이B에 가까워집니다.

이는 풀이A는 문자열을 읽는 과정을 회피했기 때문입니다. 그건 IC와 같은 잘못된 입력이 들어오지 않는다는 운좋게 주어진 조건에 의존했기에 가능합니다. 풀이A는 문제를 분해하지 않고, 딱 이 문제에만 쓸수 있는 트릭 하나를 이용해서 푼 결과입니다. 풀이A는 기반 조건이 약간만 바뀌어도 바로 무너져버릴 위태로운 구조물입니다.

똑똑한 풀이라면서 이렇게 질타하는게 좀 이상하게 보일 수 있습니다. ‘똑똑’보단 ‘교묘’가 더 정확한 표현일 겁니다. 사실 어떤 문제는 교묘하게 푸는 방법밖에 안 보이기도 합니다. 레벨 4 이상의 어려운 문제들이 그렇습니다. 그런 경우엔 어쩔 수 없죠. 하지만 그런 문제마저도 교묘하지 않게 푸는게 더 어렵습니다. 코드를 보면 왜 맞는지 바로 알수있도록, 복잡한 문제를 단순한 조각들로 나누어야 할테니까요.

다시 돌아와서, 우리는 레벨 2 이하의 문제에 대해 이야기하고 있었습니다. 이런 쉬운 문제를 굳이 교묘하게 푸는건 변호하기 어렵습니다. 물론 교묘하게 풀 수도, 단순하게 풀 수도 있으면 괜찮습니다. 하지만 제 멘티가 그랬던 것처럼 후자를 못하면 안됩니다.

서두에 말했었죠. 실무에선 레벨 2 이하의 문제들을 반복해야 한다고요. 반복은 매 시행을 자명하고 쉽게 할수 있을때 가능한 것입니다. 실무를 능숙하게 해내는 개발자들을 찾기가 생각보다 어려운 이유가 보이죠?

이제 반대로 풀이B의 장점을 생각해보죠. 풀이B는 로마 숫자의 성질을 자세히 탐구하지 않고도 생각해낼 수 있습니다. 만약 풀이A가 이 문제에 대한 유일한 정답이었다면, 저는 문제를 푸는데 시간을 꽤 썼을 겁니다. 저 교묘한 성질 하나를 발견해내야만 하니 말이죠. 문제를 풀어온 멘티들도 오래 고민하고 풀이A를 찾아낼 수 있었습니다.

반면 저는 문제를 읽으면서 풀이B 떠올릴 수 있었습니다. 그래서 풀이A같은 묘수를 찾으려는 시도조차 하지않았습니다. 실제로 코딩 테스트 중이었다면 문제를 다 읽자마자 풀이B를 써내려갔겠죠. 왜 풀이B는 문제를 읽으면서 생각해낼수 있을까요?

풀이B의 논리는 큼지막하게 잘 나뉘어져 있습니다. 저는 ‘파싱하고 다 더하면 되겠네’라고 생각했습니다. 파싱Parsing은 앞서말한 문자열을 읽는 과정을 말합니다. 어려운 파싱도 있고 쉬운 파싱도 있는데요, 이 문제에서 요구하는 파싱은 아주 쉬운 형태입니다.

사실 파싱이란 단어는 몰라도 됩니다. 모르고도 파싱을 매번 잘 해내고 있는 사람들이 있습니다. 중요한건 파싱을 해야겠다는 생각 자체입니다. 그 생각은 문제를 반으로 일도양단합니다.
Roman To Int는 문자열을 파싱하고, 그 결과로 나온 토큰(C, IV 등)들에 대응되는 숫자들을 합산하는 문제입니다.

파싱을 모르는 사람이 Roman To Int를 마주쳤습니다.
풀이A로 풀면, 여전히 파싱을 모릅니다. Roman To Int라는 특정 문제의 TMI를 알게될 뿐입니다.
풀이B로 풀면, 파싱이라는 일반적인 문제에 첫걸음을 내딛게 됩니다.

물론 푸는데도 급급한데, 장래에 더 도움될 풀이를 선택하란건 무리한 요구겠죠? 일단은 어떻게든 풉시다. 그리고 한숨 돌린 다음, 아래에 소개하는 방법들을 이용해 단순히 문제 하나 푼것 이상의 배움을 얻어냅시다. 그리고나서 다음 문제로 넘어가는 거죠.

뽕을 뽑는 방법

첫번째, 자신의 풀이를 설명해보세요. 어려운 문제를 풀때는 시간이 오래 걸리는 건 당연합니다. 하지만, 문제를 제대로 이해하고 풀었다면, 그 풀이에 대한 설명은 술술 나와야합니다. 각 코드가 문제의 어느 부분 때문에 필요한지 설명할 수 있어야겠죠.

제 멘티분들은 필요없는 코드를 풀이에 포함시키는 경우가 많았습니다. 이 코드가 왜 필요하냐고 하면 제대로된 대답을 하지 못했습니다. 이 과정을 거치면서 그런 코드들을 제거할 수 있습니다. 반대로 말해, 설명을 잘 하려면 코드가 잘 짜여져 있어야합니다. 설명이 어렵다면 잘 못 짰다는 반증인 셈이죠. 잘짠 코드는 스스로 주석없이도 문제의 어떤 조건에 의해 자신이 정당화되는지를 나타내고 있을 겁니다.

두번째, 유리한 조건을 뺀 더 어려운 문제를 상상해보세요. 어떤 조건을 만족하는 경우의 수를 세는 문제들을 많이 보셨을 겁니다. 그런 문제들이 경우를 세는 것에 그치지 않고, 모든 경우를 나열하라고 하면 문제가 약간 까다로워지죠. 이때 원래 문제를 잘 분해해서 풀었다면, 바뀐 조건에 대응해서 어느 부분을 고쳐야하는지가 바로 눈에 들어올 겁니다. 그래서 문제가 바뀐만큼만 풀이를 바꿀 수 있겠죠. 제가 약간 바뀐 문제를 멘티들에게 숙제로 냈을때, 갈팡질팡하며 기존의 풀이를 거의 활용하지 못하는 경우를 많이 보았습니다. 아마 기존의 풀이를 설명하라고 했다면 제대로 못했을거라고 확신합니다.

반대로 별거 아닌 조건처럼 보이는데, 그걸 빼면 문제의 난이도가 급상승하는 경우도 흔합니다. 이때는 그 조건들이 문제에서 어떤 역할을 하는지를 고민해보세요. 나중에 다른 문제를 풀때도 어느 부분이 열쇠 구멍인지 파악하는데 도움이 될 것입니다.

지금까지 알고리즘 문제 하나로 뽕을 뽑는 방법이었습니다. 한 문제 풀때마다 사소한 배움이라도 차곡차곡 쌓는다면, 꾸준히 실력이 느는 자신을 발견하리라 믿습니다. 화이팅입니다.