[B급 프로그래머] (Quora) 구글 또는 아마존에 다니는 경력 개발자들이 가장 유용하다고 생각하는 자료 구조는?

(그림은 (MIT) 6.851: Advanced Data Structures에서...)

Can anyone at Google or Amazon share what algorithms you find most useful over the years of your career?(구글 또는 아마존에 다니는 경력 개발자들이 가장 유용하다고 생각하는 자료 구조는?)라는 흥미로운 질문과 대답을 읽다가 독자 여러분들이 생각나서 간략하게 정리해본다. (참고로 답변을 다신 분은 마이크로소프트, 구글, 페북에 근무한 경력 소유자다)

• set/map: 코딩 과정에서 가장 중요한 자료 구조로 빠르게 값을 찾고, 값의 존재 유무를 확인할 수 있다. 물론 자세한 내부 구조는 몰라도 되지만 코드를 명확하고 효율적으로 작성하기 위해서는 언제 어떻게 사용할지 알고 있어야 한다. (본인 생각 추가: 키-쌍 NoSQL 데이터베이스를 다룰 때도 map 개념은 상당히 유용하다)
• tree: 디렉터리에 있는 파일을 재귀적으로 순회하거나, JSON 객체나 XML 문서, 아니면 산술 연산이나 표현식을 다룰 때도 상당히 중요하다. RB(Red-Black) 트리 구현 방법은 몰라도 되지만 정렬된 set이나 map이 필요한 상황에서 문제를 풀기 위한 수단으로 사용법은 잘 알고 있어야 한다. (본인 생각 추가: DOM(Document Object Model)을 이해하고 탐색하는 과정에서도 tree가 한 몫을 담당한다)
• graph: 엔티티 사이의 관계를 파악해야 하는 문제가 있을 경우 만능 해법이다. 소셜 네트워크, 컴퓨터 네트워크, 짝 짓기와 경매 시스템에 광범위하게 적용할 수 있다. 그래프는 특정 영역에 국한된 문제의 표현 방식을 일반적인 해법을 적용할 수 있는 일반화된 프레임워크로 전환할 수 있기에 강력한 위력을 발휘한다. 최단 비행 경로, 최단 도로 경로, 네트워크에서 최단 라우팅 경로는 실제로 최단 거리 계산이라는 동일한 알고리즘으로 표현할 수 있다. (본인 생각 추가: 요즘 뜨는 암호화폐의 부정 거래를 추적하는 과정에서도 그래프가 강력한 위력을 발휘한다)
• 이진 탐색: 이진 탐색은 (정렬된 트리나 벡터에서) 어떤 값이 너무 적거나 많지 않은지를 기준으로 빠르게 정확한 값을 찾는 효과적인 수단이다. 이진 트리 탐색에 연결시킬 경우 효과적으로 트리의 특정 원을 탐색할 수 있게 된다.

독자 여러분들께서도 평상시에 많이 사용하는 자료 구조가 있는지? 데이터베이스를 많이 사용하는 분이라면 SQL등을 효과적으로 작성하고 수행하기 위해 관계형 모델도 잘 숙지하고 있으면 큰 도움이 되리라는 생각이다.

보너스: 10 Common Data Structures Explained with Videos + Exercises를 읽어보면 자주 사용하는 자료 구조에 대한 기억을 되살릴 수 있을 것이다.

EOB