알고리즘 문제 하나로 뽕을 뽑는 방법

F-Lab : 상위 1% 개발자들의 멘토링

2023-10-27

개요

안녕하세요. 저는 F-Lab에서 맨토링을 하고 있는 Young이라고 합니다.

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

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

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

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

똑똑한 풀이와 멍청한 풀이

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

멘티 분이 풀어온 문제 중에 ‘leetcode’ 의 ‘Roman To Int’ 라는 문제가 있었습니다. 로마 숫자를 읽어서 우리에게 익숙한 십진법으로 출력하는 문제인데요. 여기(https://leetcode.com/problems/roman-to-integer)서 문제의 전체 내용을 확인할 수 있습니다.

로마 숫자 읽는 방법을 대강은 알고 계실겁니다.

‘I’ 는 1
‘X’ 는 10
‘C’ 는 100

에 대응되는 방식의 규칙이 있고, 대응시킨 다음에 다 더하면 됩니다. 가령 ‘CXXIII’ 는 123입니다. 여기까지 보면 너무 쉽죠? 예외 사항이 있는데, ‘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’ 라고 부르겠습니다.

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

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

가령, ‘Roman To Int’ 가 아닌, ‘Chinese To Int’ 라는 변형 문제가 나오더라도, 풀이 B는 dictionary를 수정하는 것만으로 대응가능합니다.

이는 문제를 큰 덩어리로 나눠서 풀었기 때문에 가능합니다.

문자열을 읽는 부분, 즉 문자열을 의미를 가진 부분 문자열로 나누는 부분과 나뉜 문자열로 합산하는 과정을 나뉘어 있습니다.

그리고 그 합산에 필요한 규칙, 로마자와 숫자의 대응도 dictionary 변수로 나누어져 있습니다. 그래서 문제가 부분적으로 바뀌었을 때, 풀이도 거기 대응하는 부분만 바꾸면 됩니다.

여기엔 이런 반론이 가능하겠죠.

알고리즘 문제에 ‘확장’과 ‘변경’을 고려하는게 과연 의미가 있는가?

풀이 A든 풀이 B든, 한번 풀었으면 일주일 뒤에 안 볼 거라는 걸 생각하면, 맞습니다. 하지만 확장과 변경은 문제를 푸는 도중에도 일어납니다.

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

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

이는 풀이 A는 ‘문자열을 읽는’ 과정을 회피했기 때문입니다.

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

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

실무에선 레벨 2 이하의 문제들을 ‘반복’해야 한다.

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

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

이제 반대로 풀이 B의 장점을 생각해보죠.

풀이 B는 로마 숫자의 성질을 자세히 탐구하지 않고도 생각해낼 수 있습니다.

만약 풀이 A가 이 문제에 대한 유일한 정답이었다면, 저는 문제를 푸는데 시간을 꽤 썼을 겁니다. 저 교묘한 성질 하나를 발견해내야만 하니 말이죠. 문제를 풀어 온 멘티들도 오래 고민하고 풀이 A를 찾아낼 수 있었습니다. 대신, 저는 문제를 읽는 도중에 풀이 B를 떠올렸습니다.

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

풀이 B의 논리는 큼지막하게 잘 나뉘어져 있습니다.

저는 문제를 읽으면서 ‘파싱하고 다 더하면 되겠네’라고 생각했습니다. 파싱 Parsing은 앞서 말한 ‘문자열을 읽는’ 과정을 말합니다. 어려운 파싱도 있고 쉬운 파싱도 있는데요, 이 문제에서 요구하는 파싱은 아주 쉬운 형태입니다.

사실 파싱이란 단어는 몰라도 됩니다. 모르고도 파싱을 매번 잘 해내고 있는 사람들이 있습니다. 중요한 건 파싱을 해야겠다는 생각 자체입니다. 그 생각은 문제를 반으로 일도양단합니다. 나머지 해야 할 일은 디테일을 완성하는 것뿐이죠.

파싱을 모르는 사람이 ‘Roman To Int’를 마주쳤다고 생각해 봅시다. 풀이 A로 풀면, 여전히 파싱을 모르게 됩니다. ‘Roman To Int’라는 특정 문제의 TMI를 알게되는것 뿐입니다. 풀이 B로 풀면, 파싱이라는 일반적인 문제를 다루는 방법을 익히는 것에 첫걸음을 내딛게 됩니다.

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

마무리

첫번째, 자신의 풀이를 설명해보세요.

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

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

두번째, 유리한 조건을 뺀 더 어려운 문제를 상상해보세요.

어떤 조건을 만족하는 경우를 세는 문제들을 많이 보셨을 겁니다. 그런 문제들이 경우를 세는 것에 그치지 않고, 모든 경우를 나열하라고 하면 문제가 약간 까다로워지죠. 이때 원래 문제를 잘 분해해서 풀었다면, 바뀐 조건에 대응해서 어느 부분을 고쳐야하는지가 바로 눈에 들어올 겁니다.

그래서 문제가 바뀐만큼만 풀이를 바꿀 수 있겠죠. 제가 약간 바뀐 문제를 멘티들에게 숙제로 냈을때, 갈팡질팡하며 기존의 풀이를 거의 활용하지 못하는 경우를 많이 보았습니다. 아마 기존의 풀이를 설명하라고 했다면 제대로 못했을거라고 확신합니다.

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

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