자기주도적 문제 풀이

# 근거 있는 확신

“확실해? 근거가 뭐야?” 오늘 내가 가장 많이 한 말이다. 영어학원에서 선생님의 질문에 답변하는 사람이 몇 없는데, 자신이 그중 한 명이며, 한 번 답을 하면 꼬리에 꼬리를 무는 질문 세례를 받아서 종종 킹받는다는 멘티. 그의 영어 선생님처럼 나도 오늘 그에게 질문을 쏟아냈다. 멘티보다 멘토가 더 많은 질문을 하는 멘토링. 그게 내 방식이다.

멘티가 문제 푸는 모습을 지켜보자면, 꼭 시간 제한이 있을 때 쫓기듯 알고리즘 문제 풀이(PS)를 하는 내 모습을 보는 듯하다. 대충 감으로 때려 맞추거나, 발견법(heuristic)의 요행을 바라며 체계적인 접근을 하지 않는 내 모습. "급할수록 돌아가라"는 옛 선인의 말씀은 내게 오기까지 너무 돌아온 나머지, 시간을 다 쏟아붓고 난 뒤에야 떠오르기 마련이다.

오늘 문제 풀이가 딱 그랬다. https://www.acmicpc.net/problem/2473

2473번: 세 용액

1. 투 포인터의 간격을 줄일 때, ‘두 가지 선택지’ 중 이분 탐색으로 최적의 중간값을 포함한 합이 0에 더 가까운 쪽을 골라 같은 작업을 반복하면서 0에 가장 가까운 값을 갱신한다.
2. 투 포인터의 간격이 줄어드는 방식에 Greedy함이 있어야 논리적으로 올바른 풀이인데, Greedy함이 있는지 여부를 제대로 확인도 안 하고, 냅다 제출해버렸다.
3. "O(NlogN)의 시간 복잡도여야 통과될 것이다. 그런데 그런 방법은 이 풀이밖에 안 떠오른다." 가 제출을 정당화하는 명분이었다. 결과는 "이 정도면 맞지 않을까?" 하고 제출했을 때 높은 확률로 마주하는 바로 그 결과였다.

import sys
from typing import Tuple

input = sys.stdin.readline


def solution() -> Tuple[int]:
    val_list.sort()
    lp, rp = 0, n - 1
    mp = binary_search(lp, rp)
    best_mix = (val_list[lp], val_list[mp], val_list[rp])
    best_sum = abs(sum(best_mix))
    while lp < rp - 2:
        mp_a = binary_search(lp + 1, rp)
        mp_b = binary_search(lp, rp - 1)
        next_mix_a = (val_list[lp + 1], val_list[mp_a], val_list[rp])
        next_mix_b = (val_list[lp], val_list[mp_b], val_list[rp - 1])
        next_sum_a = abs(sum(next_mix_a))
        next_sum_b = abs(sum(next_mix_b))
        if next_sum_a < next_sum_b:
            next_sum = next_sum_a
            next_mix = next_mix_a
            lp += 1
        else:
            next_sum = next_sum_b
            next_mix = next_mix_b
            rp -= 1

        if next_sum < best_sum:
            best_sum = next_sum
            best_mix = next_mix

    return best_mix


def binary_search(lp: int, rp: int) -> int:
    target = -(val_list[lp] + val_list[rp])
    start, end = lp + 1, rp - 1
    while start <= end:
        mid = start + (end - start) // 2
        if target < val_list[mid]:
            end = mid - 1
        elif target > val_list[mid]:
            start = mid + 1
        else:
            return mid

    candidates = []
    for dx in range(-1, 2, 1):
        cdd = mid + dx
        if lp < cdd < rp:
            candidates.append((abs(target - val_list[cdd]), cdd))
    candidates.sort()

    return candidates[0][1]


if __name__ == '__main__':
    n = int(input())
    val_list = list(map(int, input().split()))

    print(*solution())

범용적으로 사용할 수 있는, 수학문제 풀이 방식 선택의 근거를 멘티에게 말해주었다. 예를 들어 미지수와 방정식(1,2차든 지수-로그든)의 개수를 세어 보면, 연립 방정식으로 풀지 다른 풀이를 떠올릴지 결정할 수 있다. 수학문제를 처음 접했을 때의 막막함과 초조함을 덜어낼 수 있는 확실한 방법이다. 이걸 들은 멘티는 말했다. "와, 이런 거는 학원에서 안 가르쳐주던데요" 나는 누구한테 배웠는지 생각해 봤다. 고등학교 수학 선생님의 덕이었다. 하지만 앞으로는 웬만큼 중요한 것들 중 대부분은 스스로 터득해야 할 것이다.

'어느 정도까지 확실해야 하는가'에 관해서는 항상 고민이지만, 그 결론이 늘 미심쩍다고 해서 무의미한 것은 아니다. 그런 고민을 안고 있어야 비로소, 확실함을 위한 근거를 찾으리라 마음 먹고 노선을 점검할 수 있기 때문이다. 근거가 마련되고 나면 앞으로의 전개 과정에 집중할 수 있기 때문이다. 그래서 나는 다음 멘토링 때도 물을 것이다. "확실해? 근거가 뭐야?" 오늘의 나, 내일의 나에게도 자문할 질문이다.


# 뇌 사용량 최소화

"펜을 쥐었으면 좀 써라" 오늘 내가 두 번째로 많이 한 말이다. 펜을 쥔 손으로 연신 머리만 쥐어뜯는 멘티의 모습이 답답하면서도 익숙했다. '머릿속에 있는 걸 종이에다 써 놓고 봐야 그 속에 담긴 의미와 해법이 잘 보일 텐데' 싶다가 어느 순간 생각이 들었다. "어, 나잖아?" 노트북 자판을 앞에 둔 채 눈을 감고 머리를 움켜쥐던 내 모습이 떠올랐다.

눈을 감는 것은 시각 정보를 입력 받지 않아서 뇌 사용량이 줄어든다는 의식적 대응, 머리를 움켜쥐는 것은 머리가 띵해서 일어나는 무의식적 반응이었다. 한 달쯤 전에 깨달은 바로는, 생각은 어떤 형태로든 시각화해야 한다. 그 이유는 첫째로 문제 풀이를 위한 로직을 전반적으로 다 생각해 놓더라도, 로직의 세부 구조를 구현하느라 진땀을 빼고 나면, 예정해 놓았던 다음 부분들을 잊어버려서 다시 떠올려야 하는 소요가 있다. 망각과 재인출은 컴퓨터의 CPU에서는 발생할 일이 없는 낭비이다. 레지스터(Register)에 해야 할 작업들을 다 넣어놓고 순차적으로 바로바로 꺼내서 처리한다. 인간에게는 뇌 대신 메모장이 성능 좋은 레지스터다.

둘째로 머릿속에 있을 때는 '이게 말이 되는 생각인지, 내가 실현할 수 있는 아이디어인지'가 상당히 모호하다. 그런 고민도 은근히 시간과 정신력을 많이 잡아먹는다. 내 발상의 성공 가능성은, 그것을 언어로 옮기는 과정에서 겪는 어려움에 반비례하는 경향이 있다. 도무지 언어로 표현할 엄두가 안 나는 생각이라면, 머릿속으로 쳇바퀴를 돌려봐야 괜히 힘만 뺄 우려가 있는 셈이다. 우리 멘티가 오늘 가장 많이 한 말은 이것이다. "아 생각이 났는데, 이게 되는지 모르겠어요." 그때마다 나는 말했다. "종이에다가 좀 써 봐"

이런 이점이 있음을 알게 되어 신경 쓰고 있음에도 불구하고, 여전히 '떠오르는 생각을 눈에 보이게 쓰기'는 최대한 피하고 싶은 작업이다. 여태 잘 안 하던 작업이다 보니 익숙치 않기 때문일 수도 있다. 하지만 더 큰 이유는, 아무래도 '좋은 것만 눈 앞에 꺼내 보이고 싶은 마음' 때문일 테다. 기껏 써 놓은 생각 또는 풀이가 알고 보니 터무니 없거나 오답인 경우 자신에게 쪽팔린다. 이 감정은 머릿속에 떠올라서 곱씹어 보다가 기각하거나 망각할 때에는 느끼지 못하던 것이다. 문제 풀이에 하등 도움되지 않는 감정이 문제 풀이에 크나큰 지장을 주는 것이다. 불필요한 자기 검열일 뿐이라고 여기자.


# 머리 박고 삽질 하자

나는 물었다. "이 문제는 얼마나 고민하다가 해설을 본 거야?" 멘티는 대답했다. "30초... 아니 5분이요." 나는 말했다. "30초나 5분이나 도긴개긴이야." 심심하면 답지를 찾는 행동은, 머릿속에 떠오르는 생각을 머리로만 고민하는 것과 비슷한 이유에서 나왔을 테다. 정답일지 아닐지도 모를 풀이 과정을, 설령 정답이라고 해도 정석일지 아닐지 모르는 풀이 과정에 몰입해서 따라가는 일이, 귀찮거나 쪽팔리기 때문이다. 나도 그런 심리가 강하게 작용할 때면 "쫌만 볼까" 하며 구글을 찾는다.

하지만 직접 부딪치고 깨우쳤을 때 얻는 지식의 양질과 뿌듯함은, 솔루션에 의존했을 때 얻는 것과 비교할 수 없다. 또한 솔루션에 의존하는 것이 습관이 되면 실제 시험에서도, 책가방 안에 있는 해설지를 떠올리게 된다. 내가 자기주도적으로 PS 접근법과 알고리즘을 떠올리고 코딩하기를 원하듯, 멘티도 자기주도적으로 문제 풀이를 하고 싶어 한다. 실전에서 그렇게 하기 위해선 많은 훈련이 필요할 것이다. 별로 어려운 것 같지도 않은 문제에 막히는 자신의 초라함, 별로 많은 것을 해낸 것 같지도 않은 하루가 주는 허탈함을 견뎌야 할 것이다.

나는 멘티가 기피하는 그 시간을 함께 이끌어 가는 일에 중점을 둔다. 정석적인 풀이를 제공받거나 찾지 않아도, 멘티가 스스로 머리 박고 이리 저리 삽질해도 어느 순간 해법을 찾을 수 있음을 보여주려고 노력한다. 내가 하루 이틀 넘게 투자해서 수학 한 문제, 알고리즘 한 문제 풀던 몇몇의 나날들처럼 말이다. 결국 자기 머릿속에 어렴풋이 떠올랐던 생각에 문제 해결의 실마리가 있었음을 알게 된, 그 생각을 능히 꺼내놓을 수 있음을 알게 된, 멘티의 후련한 웃음에 내 마음도 편해졌다. 나도 그런 후련한 웃음을 짓기 위해 1일 1문제를 한다.