8퍼센트 개발 면접문제를 풀어보자
Recursive function의 이해
핑퐁 게임 (반드시 Python으로 작성할 것)
일련의 숫자가 있고, 이 숫자는 1씩 증가, 또는 감소한다. n번째의 숫자가 있을 시에, 이 숫자가 7의 배수(7, 14, 21,...)거나 7이란 숫자를 포함할 시에 (7, 17, 27,...) 방향을 바꾼다.
즉, 1, 2, 3, 4, 5, 6, [7], 6, 5, 4, 3, 2, 1, [0], 1, 2, [3], 2, 1, 0, [-1], 0, 1
과 같이 숫자는 진행한다. (첫 번째 7은 7번째, 두 번째 0은 14번째, 세 번째 3은 17번째, 네 번째 -1은 21번째)
다음의 제약 하에 pingpong(x)의 함수를 작성하라. 예시의 인풋과 아웃풋은 다음과 같다.
pingpong(8) = 6
pingpong(22) = 0
pingpong(68) = 2
pingpong(100) = 2
For Loop 또는 Array 를 쓰지 말 것.
Assignment 를 쓰지 말 것. 즉, 변수 할당을 하지 말 것.
String 을 쓰지 말 것.
첫 만남
8퍼센트 개발팀 채널에서 우연히 면접문제 파일을 만나게 되었다. 당시(3월 중순) 나는 정용은의 Python 강의 2주 차(4시간)를 들었다. Python 강의는 비전공자를 대상으로 한 상당히 알찬 강의였지만 당시엔 기초문법(if, loop 등)만 배웠다. 내 skill set 은 VBA, Matlab, E-views, LaTeX 정도. 그냥 경제학도였다. Python은 단지 내 컴퓨터에 깔려있는 상태.
Array를 쓰지 말라는 건 vector 개념으로 접근하지 말라는 뜻으로 보인다. Assignment는 뭔지 모르겠지만, 변수 할당을 하지 말라는 말은 input 이외의 변수를 사용하지 말라는 뜻으로 보인다. String은 엑셀에서의 FIND 같은 문자열을 다루는 함수를 사용하지 말라는 뜻이겠지. '7이란 숫자를 포함할 시'라는 것을 텍스트 함수를 써서 판단하지 말라는 것 같다.
숫자의 규칙을 보자. '방향을 바꾼다.'라고 표현되어있는 것은 +1 혹은 -1 이 뒤바뀐다는 뜻이다. 방향을 바꾸는 두 가지 조건이 얽혀 불규칙해 보인다. 바뀌는 방향의 일반항을 구하는 방법이 있을지 모르겠지만 문제의 의도는 일반항을 구하라는 것이 당연히 아니겠지. 그렇다면 '방향의 유지' 혹은 '방향의 전환'을 판단하기 위해서는 '방향'을 기억해야 하는데, 새로운 변수를 만들어 저장할 수 없다면 이 문제는 recursive function으로 풀어야만 할 것 같다.
힌트, 힌트가 필요하다
약간의 힌트를 얻고자 CTO 이호성님께 물어보았다.
성호 : 변수 할당을 하지 말라는 것은.. 그러니까 새로운 변수를 지정하지 말라는 뜻이 맞나요? (바보스러운 질문이다.)
호성 : 네.
성호 : 그렇다면 이 문제는 recursive function으로 풀라는 뜻이겠네요?
호성 : 그럴 수도 있고 iteration으로 풀어도 됩니다.
성호 : while loop를 쓴다고 하면 i를 써도 되나요?
호성 : i라는 변수를 할당하는 것은 안됩니다. 한 번 풀어보시죠. (미소)
i를 쓰면 안 된다니, 그럼 iteration으로 어떻게 푼다는 것이지? 전혀 감이 오지 않는다. Recursive function으로 간다.
Recursive function이란?
금융이 베이스이면서 코딩이 필요한 주니어 포지션 면접을 보게 된다면 최대로 어려운 질문이 recursive function이다. 개발 포지션이 아니기 때문에 간단한 문제가 나온다. 피보나치 수열이나 팩토리얼(factorial)을 계산하는 함수를 만드는 정도이다. 먼저 VBA로 가볍게 n! 함수를 만들어보자.
n!을 계산하는 함수를 VBA로 코딩해보자. Recursive function 은 고등학교때 배운 점화식을 함수로 표현한 것이다.while, for loop를 이용해 반복이 함수 내에서 된다면 iterative function, 함수 자체가 반복된다면 recursive function이라고 구분한다. 일반적으로 iterative function은 속도가 빠르고 recursive function은 가독성이 좋은 장점이 있다. pingpong 함수를 recursive function으로 작성한다면 다음과 같이 시작하면 좋겠다.
첫번째 항은 1, 두번째 항은 2를 반환한다.방향의 전환을 판단해보자
(n-1)항에서 방향이 바뀌는 경우는 (n-1)이 7의 배수이거나 7이라는 숫자를 포함하고 있는 경우이다. 우선 (n-1)을 1000 미만의 숫자라고 제한한다면 다음과 같은 판단문을 넣을 수 있다.
7의 배수가 아니고, 일의 자리 숫자가 7이 아니고, 십의 자리 숫자가 7이 아니고, 백의 자리 숫자가 7이 아니라면 방향미전환. 그렇지 않으면 방향전환.나머지를 구하는 % operator, 버림을 하는 int를 이용해 간단하게 표현하였다.
수열의 규칙이 무엇일까?
(n-1)항에서 방향이 바뀌지 않는다면, (n-2)항에서 (n-1)항의 증분(increment)만큼 (n-1)항에서 증가시켜 n항을 구하면 될 것 같다. 방향이 바뀐다면, (n-2)항에서 (n-1)항의 증분(increment)만큼 (n-1)항에서 감소시켜 n항을 구하면 될 것 같다.
점화식을 찾아라.위 세 부분을 잘 정리해주면 pingpong(n) 함수 완성!
pingpong(n) 함수. 겨우 열 줄이지만 쉽지않다.자, 이제 문제에서 요구한 결과가 나오는지 돌려 보자. n에 8, 22를 넣어보면 다 풀었다고 생각했지만 68을 넣는 순간 이야기가 달라진다. 상당한 시간이 지나도 결과를 출력하지 않는다. 이런. Recursive function의 속도 문제가 이런 것이구나. 한참을 돌리고 출근했더니 맞는 결과가 나와있었다. 시간을 측정해보지 않더라도 100은 도저히 엄두가 나지 않았다.
다시 선문답
성호 : 호성님! pingpong 함수는 결과가 어느 정도 시간안에 나와야 하나요?
호성 : (두 눈을 깜빡이며) 눈 깜짝할 사이? (빙긋)
성호 : 아하하 그렇군요.
IUEditor를 개발하는 JDLab 의 양주동 대표님이 슬쩍 보시더니 'recursive function에서 n이 선형적으로 증가(linearly increasing)할 때 계산량이 지수적으로 증가(exponentially increasing)하지 않아야 한다.'는 힌트를 주셨다. 핑퐁 게임은 사실 여기서부터 시작이었다.
함수의 관찰
pingpong(n) 함수를 자세히 들여다보자. 두 가지 특징을 발견할 수 있다.
1. 방향이 전환되는 경우에는 단순히 (n-2)항을 반환하면 되기 때문에 계산량이 가볍다.
2. 방향이 전환되지 않는 경우에는 이전 함수의 증분(increment)을 구한 후에 더하는 작업을 한다.
결국 포인트는 2번을 어떻게 처리하는지에 달려있다. 증분을 구해서 더한다는 것을 수학적으로 생각해보면 함수를 미분을 한 후에 다시 적분을 하는 과정이라고 생각할 수 있겠다. 잠깐, 왜 멀쩡한 함수를 미분을 하고 다시 적분을 하고 있지?
재구성
증분만을 계산하는 함수를 pingpong1(n) 으로 다시 만들어보자.
+1 혹은 -1 값만 반환하는 미분 함수적분을 계산하는 함수 pingpong2(n)을 미분함수 pingpong1(n)를 더해 만들어보자.
미분 함수를 더해서 만들어진 적분 함수pingpong2(100) = 2 의 결과를 '눈 깜짝할 사이'에 출력할 수 있게 되었다. 그렇다면 1000도 가능할까? n이 999 이상인 경우에는 에러가 발생했다. 호성님 말씀으로는 Python이 recursive function에 1000회 제한이 걸려있어서 그렇다고 한다. 아, 그렇다면 처음에 간단하게 시작하려고 했던 1000 미만 숫자 제한조건은 굳이 풀 필요가 없는 것이구나.
느낀 점
처음에는 여러 가지 제약조건이 너무 어려워서 '아니 도대체 이런 제약은 왜 있는 것이지?'라고 생각했다. 그런데 계산이 수 시간 지속되는 것을 보고 프로그래밍이란 주어진 상황과 하드웨어의 제약 하에 논리적인 사고를 전개하는 것이라는 것을 깨달았다. 그런 관점에서 예산 제약(budget constraints) 하에서 효용 극대화(utility maximization) 등 최적화를 하는 경제학 개념들과 유사한 느낌이다.
참, 눈 깜짝할 사이는 엄청나게 짧은 시간이면서 또 생각보다 긴 시간이구나.
