내가 실전에서 사용하는 자료구조와 알고리즘
(blog.pragmaticengineer.com)종종 인터뷰에서 물어보는 알고리즘 질문들이 실전에서는 안 쓰인다고 얘기되는데,
필자가 실제로 Skype/Uber 등에서 일하며 자주 사용했던 것들을 예제와 함께 정리하고 기초로 읽을 것들 추천
그래프와 그래프 탐색 : Skype & Uber
가중그래프와 최단거리 : SkyScanner
정렬 : Skype
해쉬테이블과 해슁 : 모든 곳
스택과 큐 : 때때로
암호화(Crypto) , 확률이론과 추측, Hexagonal Grid 와 계층 인덱스 : Uber
* 인터뷰에서의 알고리즘과 자료구조에 대해
인기 있는 알고리즘이나 특이한 자료구조를 아는 것은 중요하지 않습니다.
알고리즘이란게 무엇인지 알고, Greedy 알고리즘처럼 간단한 알고리즘은 생각할 수 있어야 합니다.
해시테이블, 큐&스택 같은 기본 자료구조는 알아야 하지만, Dijkstra 나 A* 같은 특별한 알고리즘들은 외울 필요는 없습니다.
제가 정렬을 넘어선 알고리즘 들에 했던 대부분의 일은 찾아보고 이해하려고 노력하는 정도입니다.
Red-Black 이나 AVL 트리 같은 특이한 자료구조도 마찬가지구요.
실제로 이런 자료구조를 쓸 일도 없었고, 필요하다고 해도 다시 검색해서 알아볼 것입니다.
실리콘밸리에서 동적 프로그래밍이나 특이한 자료구조를 묻는 질문을 하는게 점점 더 일반적이 되어갑니다.
이런 질문이 뛰어난 엔지니어를 뽑는데는 도움이 될지 몰라도, 실제로 고급 알고리즘 지식이 필요 없는 일을 아주 잘하는 사람들을 못 뽑게 됩니다.
정말 필요한 것은, 가장 일반적인 데이터 구조에 대한 인식과 문제를 해결하기 위한 가장 간단한 알고리즘을 도구로 사용하는 능력입니다.
데이터 구조와 알고리즘은 툴셋일 뿐입니다.
소프트웨어 개발을 할때 자신있게 사용해야 하는 도구 입니다.
이런 도구들을 잘 알면, 이런 것들을 사용한 코드들을 보는데 익숙해 질겁니다.
또한 어려운 문제를 푸는 솔루션을 구현하는데 좀 더 자신감이 생길겁니다.
기본적인 것을 알기 위해 다음의 것들을 추천합니다. (링크는 댓글에)
- GeekforGeeks 의 Data Structures Overview (온라인 글 모음)
- HackerRank 의 DataStructure Collection (문제 풀며 배우기)
- Grokking Algorithms : 그림으로 개념을 이해하는 알고리즘(번역서)
- The Algorithm Design Manual 과 Algorithms: Fourth Edition 은 너무 건조하고 매일 실전에서 쓰기에는 적합하지 않아요.
- GeekforGeeks 의 Data Structures Overview
https://geeksforgeeks.org/overview-of-data-structures-set-1-linear-dat…
- HackerRank 의 DataStructure Collection
https://www.hackerrank.com/domains/data-structures
- Grokking Algorithms : 그림으로 개념을 이해하는 알고리즘
영문 : https://www.amazon.com/gp/product/1617292230/?tag=amzneu-20
한글판 (한빛미디어): https://www.hanbit.co.kr/store/books/look.php?p_code=B5896248244
The Algorithm Design Manual https://www.amazon.com/gp/product/1848000693?tag=amzneu-20
Algorithms : 4th Edition https://www.amazon.com/gp/product/032157351X/?tag=amzneu-20
- 알고리즘 개정4판 (이북) http://www.yes24.com/Product/Goods/71729526
글 초반에 나오는 Homebrew 개발자 Max Howell 이 구글 인터뷰에서 이진트리 반전을 칠판에 못써서 떨어진 일화는 아주 유명하죠.
실제 구글 개발자중 90%가 홈브루를 쓰고 있는데, 정작 개발자는 떨어진 아이러니..
그 90퍼는 homebrew개발자가 꺼냇돈 숫자고 그 트윗에 규글 개발자가 절대 90퍼가 아니라고 답변을 달앗던걸로..
어차피 구글에선 데탑은 구분투고 랩탑은 쉘머신이라 딱히 쓸 일도 없긴 하겟죠