좋은 개발자가 되기 위해서는 문제 해결 능력이 필수적입니다. 제가 쓴 책 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"에서는 다양한 문제 해결 기법과 예제들을 소개합니다.

알고리즘 인터뷰 가이드 1: 준비편

[처음으로] [모든 글 보기] [같은 카테고리의 글 보기: 구직, 알고리즘]


구글이나 마이크로소프트, 페이스북 같은 회사들은 면접에서 알고리즘 문제들을 풀고 구현하도록 시키는 것으로 유명하다. 개인적으로는 이런 주제로 면접을 보는 것이 특정 분야나 환경에 국한되지 않고 프로그래머의 역량을 볼 수 있는 기회라고 생각하지만, 막상 현업에서 항상 사용되지는 않는 주제들이다 보니 쉽게 적응하기 어려운 경우들도 있는 것 같다. 특히 면접이란 실제 업무와 다른 포맷을 갖기 때문에, 충분히 역량 있는 사람들도 면접의 '프로토콜'을 이해하지 못하면 떨어지기가 쉽다. 요즘 그런 안타까운 상황을 많이 보다 이렇게 글을 쓰게 되었다.

나도 면접을 많이 본 편은 아니지만.. 내가 면접 볼 때 준비했던 것들을 간략하게 정리해 보려고 한다. 그 외에도 문제 유형별로 준비할 점을 간략하게 요약하고, 인터넷에서 찾을 수 있거나 주변 지인에게 들은 인터뷰 문제들을 어떻게 풀어야 할지 예를 들어 보려고 한다.

여기서는 먼저 중요한 인터뷰 요령과 준비할 때 공부해야 할 주제들을 간단하게 소개하고, 관련된 문제들을 소개하겠다. 나의 해답은 다음 편에.. :-)

면접의 원칙들

면접과 필기 시험은 다르다

내 생각에 알고리즘 인터뷰를 할 때 가장 중요한 원칙은 자신이 생각하는 과정을 입 밖으로 내서 말하는 것이다. 면접과 필기 시험은 다르다. 필기 시험에서는 혼자 머릿속에서 고민에 고민을 거듭해 낸 답이 정확하기만 하면 되지만, 면접에서는 그래서는 안 된다. 면접의 가장 기본적인 목적은 면접자의 문제 해결 능력을 확인하는 것인데, 이것을 보여줄 수 있는 가장 좋은 방법은 생각하는 방향을 입밖에 내서 설명하는 것이기 때문이다. 맞는 방향을 잡지 못하고 좀 헤매더라도 상관 없으니, 능동적으로 문제를 해결해 나가는 과정을 보여주는 것이 중요하다. 흔히 곰돌이 디버깅이라고 하는 것처럼, 이렇게 자신의 사고 과정을 설명하다 보면 풀기 어려워 보였던 문제도 풀 수 있는 경우가 빈번하다.

물론 쉼없이 떠들어야 한다는 말은 아니다. 특히 모국어가 아닌 말로 면접을 봐야 할 경우 더더욱 중요해지는데, 첫 마디를 꺼내기 전에 잠깐 멈춰서 무슨 말을 할 지 되새김질 해 보면 도움이 된다.

생각의 프레임워크

자신이 생각하는 "과정"을 이야기해야 한다는 것을 부담스러워 하는 사람들이 종종 있는 것 같다. 많은 사람들은 딱히 자신이 문제를 푸는 과정이 어떤지 생각해 본 적이 없기 때문이다. 문제를 보고 적당히 고민을 해 보고 답이 떠오르면 푸는거고 아니면 말고... 이런 생각을 하는 사람들이 너무 많다. 문제를 보고 나서 답이 곧장 떠오르지 않는다면.. 아니, 답이 곧장 떠오르는 경우에도 어느 정도 체계적인 구조 안에서 자신의 해결 과정을 설명하는 것이 도움이 될 때가 있다. 예를 들어 다음과 같은 원칙들이 그것이다.

  • 단순화한 문제를 푸는 것은 많은 경우 문제 해결을 위해 필요한 직관을 얻는 데 도움이 된다. 예를 들어 두 개의 변수를 정하는 문제라면 한 개를 고정하고 다른 한 개만 찾는다거나, 입력의 크기를 아주 크게 줄인다거나 하는 방법이 있다. 이럴 때는 "문제가 쉽지 않은데, 이렇게 이렇게 더 간단한 버전부터 풀어 보고 이걸 일반화할 수 있을지 한 번 보는 것이 좋을 것 같습니다.." 라고 이야기하고 단순화한 문제를 풀어 보면 된다.
  • 효율적인 알고리즘을 생각해 내는 문제라면, 처음부터 효율적인 방법을 찾아내야 하는 문제도 있지만 간단하고 비효율적인 방법에서 시작해서 그걸 최적화해 나가는 방법도 많은 경우에 유효하다. "이 문제를 푸는 가장 단순한 방법은 ~~~겠네요. 그런데 이 방법의 시간 복잡도는 ~~라서 너무 느린데, ~~ 부분을 ~~~ 자료 구조를 대신 써서 최적화하면.." 같은 식으로 설명하면 된다.
  • 혹시라도 비슷한 문제를 들어 본 적이 있다면, "오, 그거랑 비슷한 문제를 과거에 들어본 적이 있네요. 그 문제는 ~~ 해서 풀었는데, 이 문제의 답과 연관이 있을 것 같습니다.." 라고 시작하면 된다.

다행히 인터뷰에서 주어지는 문제들은 비교적 짧은 과정을 통해 답을 얻을 수 있는 경우가 많다. 지금 이야기한 세 가지 접근 방법만 잘 써도 많은 경우 문제를 풀 수 있을 것이고.. 아닌 경우에도, 인터뷰어가 상식적일 경우 당신의 체계적인 접근 방법에 추가 점수 조금은 줄 것이다. ㅋㅋ

문제 해결 과정에 대해 더 알고 싶으면 내 책을 보면 된다. ^^;;

적절한 가정 혹은 질문하기

면접관도 사람이라 그 문제가 모호하거나 불완전한 구석이 있을 수 있다. 문제의 답에 관련된 부분이 모호하다고 생각하면 질문을 하자! 이 때 적당한 가정을 할 수 있으면 가정을 하고, 이것 또한 입밖으로 내서 확인을 받아야 한다.

예를 들어 알고리즘을 설계하는 문제를 질문으로 받았다면 입력의 크기는 얼마나 되는지, 얼마나 빨리 수행해야 하는 일인지, 메모리는 얼마나 사용해도 되는지 등등을 물어볼 수 있다. 애초에 입력의 크기가 작거나 시간 제한이 느슨하다면 무식하게 풀어도 되니까.

전화 인터뷰

외국 회사랑 면접하게 되면 흔히 있는 것이 바로 전화 인터뷰다. 외국 회사랑 면접하면 당연히 한국어를 쓸 수 없으니 전화 영어는 더더욱 답답해지는데.. 이 때는 최소한 핸즈프리랑 펜, 종이 정도를 준비하고 인터뷰에 임하는 것이 좋다. 면접 보면서 구글 검색할 생각은 왠만하면 포기하는 게 좋고. 그 외 인터넷에서 들은 충고 중 하나로, 일어서서 전화통화를 하라는 것이 있었다. 별 것 아닌거 같지만 좀 더 자신감 있는 목소리를 내게 해 준다고 한다.

문제의 유형들

프로그래밍 인터뷰에 흔히 출현하는 문제 유형은 대개 다음과 같은 것 같다.

알고리즘 설계 및 구현하기

프로그래밍 인터뷰에 흔히 출현하는 것이 이런이런 문제를 푸는 알고리즘을 설계하고 시간 복잡도를 분석하라는 것이다. 뭐 교과서에 나오는 알고리즘도 나올 수 있고, 알고리즘을 직접 고안해야 할 수도 있고 (다행히 이런 경우는 문제가 좀 더 쉬운 경우가 많다) 자료 구조 관련 문제들도 많을 것이다.

이 때 유의할 것은 대부분의 경우 실제 컴퓨터를 주고 코드를 짜는 것이 아니라 화이트보드에 설명해야 한다는 것이다. 화이트보드에 코드를 작성하는 것은 IDE에서 코드를 짜는 것과 느낌이 매우 다르니까.. 면접을 준비할 때 미리 연습해 두는 것이 좋다. 대부분의 경우 의사코드를 화이트보드에 쓰는 것으로 충분하지만, 세미콜론까지 꽉 채워서 C++ 코드를 쓰라고 한 면접관도 있었으니.. 자신이 잘 한다고 적어낸 언어는 손 코딩을 좀 연습해 두면 좋을 것이다.

이런 유형으로 나오는 문제에서 90% 정도의 질문은 학부 자료 구조+알고리즘 과목 커리큘럼으로 커버 가능하다. 다음과 같은 주제들은 정말로 단골 손님이니 동작 원리에 대해 공부해 두면 좋다. 화이트보드에 의사코드를 일사천리로 써나가고 설명할 수 있다면 두려울 게 없을 것이다.

배열 조작 관련 알고리즘

  • 정렬 알고리즘: 학부 졸업생에게 퀵소트머지소트 구현해 보라는 문제 정도는 흔히 나온다. 구현은 물론이고, 이들의 공통점(둘다 분할 정복 알고리즘이다)과 차이점(퀵소트는 분할 과정이 복잡하고, 머지소트는 병합 과정이 복잡하다) 도 알아두면 좋다.
  • 이분 탐색 알고리즘: 벤틀리가 직업 프로그래머들에게 이분 탐색을 구현하게 시켰더니 90%는 제대로 못짜더라라는 일화는 유명하다. 이만큼 구현하기 까다로우니까 신경 써서 한번 구현해 보면 좋다. 생각하는 프로그래밍에서 아주 잘 다루고 있다.
  • k번째 원소 선택 알고리즘: 퀵소트의 응용판인데 아주 유용하다. 원리를 이해해 두면 다른 문제 푸는 데도 여럿 응용 가능하다.

자료 구조

  • 스택, 큐
  • 해시: ~~에서 ~~를 빠르게 찾으려면 어떻게 할까요? 라는 질문의 절반 정도는 그냥 "해시 쓰면 안되나요?" 라고 대답할 수 있다.
  • 이진 트리: ~~에서 ~~보다 작은/큰 원소를 빠르게 찾으려면 어떻게 할까요? 라는 질문의 절반 정도는 그냥 "이진 트리 쓰면 안되나요?" 라고 대답할 수 있다.

해시나 이진 트리는 특성이나 시간 복잡도를 잘 공부해 두는 것이 좋다.

그외 준비할 것

  • 재귀 호출: 길이 N인 모든 순열 생성하기, 미로에서 길 찾기 등의 문제들은 꽤 자주 볼 수 있다. 능숙하게 쓸 수 있도록 하자.
  • 시간 복잡도 분석: 이건 뭐.. 뭘 하든 필요하다.

브레인티저

다음으로 흔한 문제 유형은 흔히 브레인 티저라고 부르는 퍼즐이다. 이런 문제들은 99.9%의 프로그래머의 현업과 아무 상관 없기 때문에, 면접에 이런 문제가 나오면 격분하는 사람들을 종종 볼 수 있다. 위에서도 말했지만, 이런 문제를 내는 것은 이 문제를 해결하는 과정을 보기 위한 것이다. 따라서 감이 안 오더라도 멍하게 있지 말고 이렇게 하면 어떨까, 저렇게 하면 어떨까 하는 식으로 문제에 접근해 가는 과정을 보여줘야 한다. 그정도는 되어야 면접관도 힌트라도 하나 더 주고 올바른 방향으로 당겨줄 수 있다. "생각의 프레임워크"에서 언급한 접근 방법을 써 보는 것도 좋다.

이거 관련해서 문제집이 여러 개 있는데 그 중 제일 유명한건 이것... 물론 개발자 면접에서 이것까지 보는 건 좀 오버인 거 같긴 하다.

디자인 문제들

디자인 문제는 주어진 작업을 수행하는 프로그램의 구조를 설명하기를 요구한다. 대개 OOP 패러다임 안에서 프로그램의 구조를 적절히 설명하면 된다. 사실 이것은 적절한 입코딩의 영역이라 내가 뭐라고 할 수 있는 주제는 아니다. 하지만 가능한한 간단한 답안을 작성하고, 요구 사항이 변함에 따라 적절히 설계를 변경해 주는 센스가 필요하다. 면접관이 보고 싶은 것은 클래스가 뭔지, protected 가 뭔지 이런 것을 아는가가 아니라, 적절한 구조를 만들어 내는가이기 때문이다. 그냥 "이렇게 해도 되긴 될텐데 이렇게 짜죠?" 가 아니라 "이런 식으로 디자인하는 것이 더 이해하기 쉽고 더 직관적이고 더 현실 세계와 가깝기 때문에 이렇게 짜죠?" 라고 말할 수 있는 것이 중요하다는 이야기다.

이런 부분 관련해서 읽어볼 수 있는 좋은 책으로 클린 코드가 있다.

차회예고

다음 포스트에서는 내가 들어본 문제들과 구글링으로 얻을 수 있는 구글 인터뷰 문제들을 풀어보도록 하겠다.


[처음으로] [모든 글 보기] [같은 카테고리의 글 보기: 구직, 알고리즘]

2012 구종만