devcken.io

Thoughts, stories and ideas.

My advice on studying algorithms

이 글은 Buck Shlegeris의 My advice on studying algorithms을 번역한 글입니다. 심한 오역이나 어색한 부분이 있을 수도 있습니다.

Buck Shlegeris

2016년 8월 14일

소프트웨어 엔지니어링 인터뷰에서는 종종 화이트보드 알고리즘 문제가 나오곤 합니다. 이 글은 그러한 알고리즘 문제를 공부하는 방법에 대한 저의 충고입니다(이 주제에 대해 제가 자격이 있다는 것을 말씀드리고 싶습니다. 저는 Google과 Apple을 포함한 많은 화이트보드 인터뷰에 통과했습니다. 프로그래머들이 이러한 알고리즘 인터뷰를 준비하도록 하는 것이 제 일의 일부입니다. 저는 매우 넓고 다양한 배경지식을 가지고 프로그래머들에 대한 200회 이상의 기술 면접을 진행해왔습니다).

Triplebyte 직원이 아닌 제 스스로가 이 포스트를 작성하고 있습니다.

인터뷰에서는 알고리즘 이외의 다른 주제도 다룹니다. 그러한 주제의 연구를 위한 유용한 정보를 담은 Triplebyte의 블로그 포스트도 있습니다. 저는 본질적으로 그 포스트의 두번째 섹션에 대한 보충 설명으로 이 글을 쓰려고 합니다.

배경: 회사들은 왜 알고리즘을 물어볼까요?

실제 삶에서, 프로그래머들이 이진 탐색 트리나 그래프 탐색 알고리즘을 구현하는 일은 없습니다. 그러면 회사들은 왜 그에 대한 질문을 그렇게나 많이하는 걸까요?

이 질문에 대해서는 내적 그리고 외적 해석이 모두 존재합니다. "회사가 알고리즘 문제를 묻는 것이 왜 유용한가"가 하나의 질문이고, "회사가 알고리즘 문제를 내기로 결정한 실제 원인에 대한 메커니즘은 무엇인가"가 또 다른 질문입니다.

저는 알고리즘 문제를 내는 이유에 대해 설명하는 것으로 시작해, 그 유행에 대해 좀 더 비꼬는 설명으로 나아가려고 합니다.

우선, 많은 프로그램들이 아주 기본적인 것을 해내지 못합니다. 예를 들면, Customer 객체 리스트가 존재하고, 각각의 객체가 Purchase 객체의 배열을 가지고 있을 때, 지난 주에 가장 많이 소비한 5명의 고객 이름을 얻고자 한다고 해보겠습니다. 추측컨대, 아마도 전문 프로그래머 중 50%는 이 문제를 30분 내에 풀지 못할 겁니다. 실수로 그러한 사람을 고용하고 싶지는 않을 겁니다.

조금 덜 비관적으로 말하자면, 프로그래밍 업무에 대해 누군가와 인터뷰할 때, 한번에 머리 속에 많은 세부사항들을 담고 있어야 하는 어렵고 복잡한 문제들을 풀 때 그들이 얼마나 잘 해낼 수 있는지 알아내려고 할 겁니다. 실제 삶에서, 몇 주씩 걸릴 만큼 큰 프로젝트를 수행하고, 소프트웨어의 서로 다른 많은 부분들에 대해 한번에 생각해야 하기 때문에, 헷갈리고 복잡한 문제가 생겨납니다. 그러나 인터뷰에서는 일반적으로 여러분이 프로그래밍 문제에 깊게 파고들 만한 충분한 시간이 주어지지 않습니다. 그래서, 규모가 있어 어려운 문제를 묻기보다는, 짧고 어려운 문제를 물어보게 됩니다.

어떻게 하면 설명하기 간단하면서도 복잡하지만 짧은 코딩 문제를 찾아낼 수 있을까요? 제가 생각하기에 알고리즘이 제격입니다. 알고리즘은 대부분의 모든 소프트웨어 엔지니어가 아는 컴퓨터 과학의 가장 복잡한 영역이며, 설명하기 쉽고 구현하기 까다로운 문제들이 많습니다.

이제부터 좀 더 냉소적인 생각을 말해보겠습니다.

인터뷰 프로세스는 어색하고 성가십니다. 엔지니어 팀은 모두 팀의 기술 인터뷰를 통과한 사람들로 구성됩니다. 그래서 모두 그들의 인터뷰 과정이 소프트웨어 엔지니어링 능력을 측정하는데 있어 굉장히 정확하다고 믿고 생각하도록 자기 합리화합니다. 그러므로 알고리즘 인터뷰 문화가 사내에 생기고 나면, 그것을 바꾸기는 어렵습니다.

모두가 알듯, 10년 전 Google에는 굉장한 팀이 있었고, 그 당시 인터뷰에서 알고리즘 문제를 냈습니다. (최고의 지원자들을 Google에 뺏기는 일이 많기에) 대부분의 회사들은 자신들이 Google이 아니라는 점에 대해 약간 불안해 합니다. 그래서 Google의 인터뷰 프로세스를 모방하려고 합니다.

최악의 경우에 알고리즘 인터뷰는 기괴하고 못살게 구는 과정으로 변질될 수 있습니다. 때때로 회사들은 어떤 무작위 수수께끼가 굉장한 지원자를 찾기 위한 비법 양념이라고 완전히 맹신하게 되며, 여러분은 그에 대한 그들의 마음을 결코 바꿀 수 없습니다.

개괄적으로 말하면, 저는 인터뷰에서 전통적인 어려운 알고리즘 문제를 내지 않습니다. 최악의 경우에 알고리즘 문제는 극히 나쁜 인터뷰 문제입니다. 제가 특히 싫어하는 문제에 관한 근거에 대해 쓴 적이 있습니다. 알고리즘 문제는 좀 더 난해하고 굉장한 통찰력을 요할 때 특히 좋지 않습니다(알고리즘 인터뷰 프로세스를 구축하고자 한다면, 주저 말고 이메일을 주세요. 이러한 문제가 없는 문제를 내는 방법에 대한 좀 더 자세한 의견을 드릴 수 있습니다).

공부 방법

편집: 이에 대한 Haseeb Qureshi의 블로그 포스트를 막 다시 읽었습니다. 그 글에 동의하며 좀 더 자세하게 설명하고 있다고 생각합니다. "General Study Strategy"와 "Programming Interview Study Guide" 섹션을 읽어보세요.

알고리즘 문제를 푸는데 두 가지 기술이 필요하다고 생각합니다. 먼저, 모든 고전 알고리즘과 데이터 구조 자료를 알아야 합니다. 두번째로, 압박 속에서 화이트보드 에 알고리즘 로직을 빠르게 만들 수 있어야 합니다. 이 주제들에 대해서 각각 알아보려고 합니다.

규범적인 알고리즘 자료

회사가 당신을 테스트하기 위한 일관되고 괜찮은 핵심 알고리즘 지식이 있습니다. 많은 좋은 프로그래머들이 이 리스트에 존재하지 않는 자료에 의존하는 문제를 모르며 그런 문제를 낼 경우 좋은 프로그래머들이 실패하게 될 것이므로 회사는 그러한 문제를 묻지 않으려 할 겁니다.

다음은 여러분이 알아야 하는 데이터 구조 자료 목록입니다:

  • 리스트 구조: 배열, 동적 배열, 연결 리스트
  • 세트와 맵 구조: 해시 맵, 이진 탐색 트리, 힙

각각의 데이터 구조에 대해, 모든 필수 메서드가 구현된 방법과 런타임에 대해 알아야 합니다(리스트의 필수 메서드에는 set, get, pushAtEnd, popAtEnd, insertByIndex, removeByIndex가 있습니다. 세트의 필수 메서드에는 insert, remove, contains?가 있습니다). 데이터 구조의 구현을 사용하는 코드를 작성할 줄 알아야 합니다. 예를 들어, 이진 탐색 트리를 가져와 트리에서 x에 가장 가까운 값을 탐색하는 getNearestElementTo(x)를 구현할 수 있어야 합니다.

이에 대한 다른 참고 사항은 다음과 같습니다:

  • 여러분의 이진 탐색 트리 구현이 균형을 위한 로직을 필요한다는 것을 알아야 하지만, 세부 사항은 몰라도 괜찮습니다(선택 자료: 자가 균형 이진 탐색 트리 구현을 빠르게 배우려면 트립에 대해 알아보세요. 레드블랙 트리가 동작하는 방식을 이해하려면, 대신 좌편향 레드블랙 트리 혹은 2-3-4 트리에 대해 알아보세요).
  • 아마도 큐를 두 개의 스택으로 구현할 수 있다는 점을 알아둬야 할 겁니다.

다음의 모든 알고리즘을 구현할 수 있어야 합니다:

  • 그래프 알고리즘: 너비 우선 탐색, 깊이 우선 탐색, 다익스트라(Dijkstra) 알고리즘
  • 한 가자 빠른 정렬 알고리즘: 병합 정렬 혹은 퀵 정렬
  • 배열에 대한 이진 탐색. 이 알고리즘은 올바르게 구현하기 까다롭지만, 대충 이해하더라도 코드를 작성해 볼 가치는 있습니다.

Big O 표기법에 익숙해져야 합니다.

이 모든 걸 어떻게 배워야 할까요? 제가 즐겨찾는 자료는 Skiena의 알고리즘 디자인 메뉴얼입니다. 위에서 말한 모든 자료를 2-6 챕터에서 다루고 있습니다. 집필 스타일이 정말 매혹적이며 제가 생각하기에 가장 중요한 자료에 초점을 맞추고 있어 좋아합니다. 이 책은 인터넷에서 자유롭게 이용할 수 있습니다. 이 책의 한 가지 단점은 책의 코드 예제가 C로 되어 있어 C를 읽을 수 없는 프로그래머들이 보기에는 어렵다는 점입니다. 이 책을 읽는다면, 1-6 챕터와 12 챕터는 꼭 읽을만한 가치가 있다고 생각됩니다. 이 책에서는 인터뷰에 나올 가능성이 극히 작은 자료를 아주 약간 다루지만, 불필요한 자료가 아주 핵심적인 것들을 돋보이게 하는 좋은 일을 한다고 생각합니다.

간결한 설명을 원한다면, Cracking the Coding Interview와 InterviewCake.com의 설명이 좋다고 생각합니다.

제 생각에는 Skiena의 책이 극도로 딱딱하고 다소 현학적인 유명한 CLRS 텍스트북보다 더 좋습니다.

여기에 그래프 알고리즘에 대한 약간의 정리를 해두었는데 유용한 리소스가 될 겁니다.

규범적인 알고리즘 스킬

앞서 인터뷰에 필수인 핵심 지식에 대해 알아봤습니다. 다음으로 학습을 위해 제가 좋아하는 리소스와 함께 테스트한 다른 종류의 프로그래밍 스킬에 대해서 알아보겠습니다.

Cracking the Coding Interview는 그 모든 것을 위한 대단히 유용한 리로스입니다. 여기에 이 책에 대해 몇 가지 메모를 해두었습니다.

다음은 알고리즘 인터뷰 문제에 대한 가장 흔한 중점 요소들입니다:

  • 동적 프로그래밍: Skiena의 책 챕터 8을 읽거나 이 주제에 대한 Cracking the Coding Interview의 챕터를 읽고 학습하세요.
  • 재귀: 이 주제에 대한 굉장한 챕터가 Cracking the Coding Interview에 있습니다.
  • 유명한 데이터 구조를 선회하기. CtCI에는 이 주제에 대해서 데이터 구조 각각에 대한 좋은 문제가 있습니다. 예를 들어, BST에 대해, CtCI의 트리 챕터를 참고 가능합니다.
  • 문제에 대한 빠른 데이터 구조를 구성하기. 이런 종류의 문제에 대한 예제가 여기 있습니다.

제가 하고자 하는 주된 조언은 Cracking the Coding Interview에 있는 문제들을 풀어보라는 것입니다. 제가 가장 중요하다고 생각했던 문제들에 관해 노트에 나열해두었습니다.

다음은 이 문제들을 공부하는 데 필요한 대략적인 참고사항입니다: 풀이를 읽어 "컨닝"을 하는 것도 괜찮다고 생각합니다. 인터뷰 연습 문제 풀이를 완전히 포기하는 것보다는 직접 풀지 않고 해답을 읽는 것이 더 낫다고 생각합니다.

알고리즘 인터뷰 성공에 관한 비기술적인 측면

실제 사람이 여러분에게 알고리즘 문제를 묻도록 하여, 압박 속에서 문제에 답하는 연습을 해볼 가치가 있습니다. 이에 대한 좀 더 많은 조언은 Triplebyte 블로그 포스트, 특히 2, 3 그리고 7번 항목을 참고하시기 바랍니다.

알고리즘과 데이터 구조에 대한 심화 학습

일자리를 얻기 위한 경제적 목적이 아니라, 스스로가 알고리즘과 데이터 구조에 심취해 있다고 가정해보겠습니다. 좀 더 배우려면 어떻게 해야 할까요?

좀 더 배우기에 가장 쉬운 것은 제가 위해서 설명했던 핵심 데이터 구조 명부에는 없는 것 중 상대적으로 간단한 데이터 구조일 겁니다. 예를 들면, 트립, 스킵 리스트, augmented BST 그리고 서로소 집합(disjoint set) 데이터 구조는 모두 이해하기에 상당히 쉽고 모두 정말 멋지다고 생각합니다.

이해하기 좀 더 어렵지만 노력을 들일 가치가 있는 데이터 구조에 대한 주제도 있습니다. 예를 들어, 이 슬라이드에서는 BTree와 2-3-4 트리를 설명하고 있습니다.

좀 더 흥미로운 데이터 구조 자료에 대한 리소스 중 제가 좋아하는 것은 다음과 같습니다:

  • Skiena 책의 챕터 12와 그 이후의 챕터들
  • 놀라운 스탠포드 클래스인 CS166. 이 슬라이드들은 놀라우며 읽기 좋습니다. 저는 몇 가지 문제 세트 풀이를 즐겼습니다. 더 많은 데이터 구조의 재미를 위해 클래스의 프로젝트 아이디어 핸드아웃을 추천합니다.
  • 저는 여기서 했던 특정 데이터 구조 문제에 관한 일들이 꽤나 자랑스럽니다. 실제로 열심히 하지는 않았지만 아마추어 활동으로 즐겼던 것입니다. 그 문제에 대한 저의 해법은 고급 데이터 구조에서 나온 몇 가지 아이디어를 수반하며 그것이 꽤나 훌륭하다고 생각합니다.

리소스