알고리듬과 자료구조 사전 (Dictionary of Algorithms and Data Structures)

 (xlinux.nist.gov)
3P by GN⁺ | ★ favorite | 댓글 1개
  • 알고리듬, 알고리듬 기법, 자료구조, 전형적 문제, 관련 정의를 모아 정리한 온라인 사전
  • Ackermann's function 같은 공통 함수를 포함한 알고리듬 항목 수록
  • traveling salesman, Byzantine generals 등 전형적 문제 항목 포함
  • 일부 항목은 구현(implementation) 및 추가 정보 링크 제공, 항목은 영역(area)과 유형(type)별 색인으로 정리
  • business data processing, AI, graphics 등 특정 분야는 제외하고 "일반(general)" 알고리듬과 자료구조에 집중

사이트 개요 및 운영 주체

  • NIST의 Information Technology Laboratory 산하 Software and Systems Division이 호스팅
  • 사전 개발은 1998년 Paul E. Black의 편집 아래 시작
  • 알고리듬, 알고리듬 기법, 자료구조, 전형적 문제 및 관련 정의를 다루는 사전 형태

수록 항목 구성

  • 알고리듬 항목에는 Ackermann's function 같은 공통 함수 포함
  • 문제 항목에는 traveling salesman, Byzantine generals 포함
  • 일부 항목은 구현(implementation) 및 추가 정보로 연결되는 링크 제공
  • 색인 페이지는 항목을 영역(area)별과 유형(type)별로 나열
  • two-level index는 전체 다운로드 용량이 본 페이지의 1/20 규모

이용 안내

  • 부정행위(cheat) 목적 사용 금지, 교사는 도움이 필요하면 연락 안내
  • 제안, 수정, 의견은 Paul Black에게 연락하도록 안내

다루지 않는 범위

  • 현재 다음 분야 특화 알고리듬은 미포함
    • business data processing, communications, operating systems 또는 distributed algorithms
    • programming languages, AI, graphics, numerical analysis
  • "일반(general)" 알고리듬과 자료구조만으로도 다루기 충분히 어렵다는 이유로 범위 한정

색인 및 참고 사항

  • n-way, m-dimensional, p-branching처럼 선행 변수가 붙은 용어는 k- 항목 아래 분류
  • A Glossary of Computer Oriented Abbreviations and Acronyms에서 유용한 항목 확인 가능

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 관련 과거 글들:
    Dictionary of Algorithms and Data Structures (1998) - https://news.ycombinator.com/item?id=12758176 - 2016년 10월 (댓글 18개)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=8905348 - 2015년 1월 (댓글 4개)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=5525893 - 2013년 4월 (댓글 15개)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2496539 - 2011년 4월 (댓글 16개)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2351074 - 2011년 3월 (댓글 1개)

  • 이 자료를 좋아하고 싶지만, 내가 아는 것 중 Fenwick tree와 union-find 알고리즘/자료구조가 빠져 있음
    Fenwick tree를 처음 본 곳은 여기였음: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
    union-find는 아마 여기서 봤던 것 같음: https://www.youtube.com/watch?v=PGZ64ob440I
    다만 기억으로는 고정 크기 배열이 아니라 딕셔너리/해시맵 구현이었음

    • 꽤 많이 빠져 있는 것 같음. Fenwick은 다른 이름으로라도 있을 줄 알았는데 안 보이고, union-find가 없는 건 더 이상함. 정말 훌륭하고 유용한 자료구조라서 숨겨져 있을 만한 다른 이름도 떠오르지 않음
      바로 생각나는 것 중 못 찾은 건 제곱근 분할, heavy-light decomposition, 그리고 범위 최솟값 질의(Range Minimum Query) 전반임. 개인적으로 범위 최솟값 질의는 일반 문제로서 가장 좋아하는 축에 들고, 시간을 들여 집중할 기법 묶음으로는 정렬보다 훨씬 흥미롭다고 봄
      union-find 자료구조는 보통 고정 배열로 보여주는 편인데, 그래야 알고리즘 분석이 좀 더 재미있어짐. 조회 비용이 O(1)을 넘으면 분석에서 재미있는 부분이 묻혀버린다고 봄. 물론 자료구조 자체는 어느 방식이든 잘 동작함
    • 유한한 모음집이니 거의 모든 게 빠질 수밖에 없음. soft heap이나 finger tree도 없고, Okasaki가 다루는 순수 함수형 자료구조도 많이 빠져 있음

  • 훌륭한 자료지만, 자료구조와 알고리즘 수업이 응용에 더 초점을 맞췄으면 좋겠음
    단순히 이것이 무엇인지 아는 것보다, 왜 유용하고 어떤 맥락에서 꺼내 써야 하는지 아는 데 더 관심이 있음

    • https://www.redblobgames.com/는 맥락을 많이 제공하면서도 기술적 세부사항을 피하지 않는 아주 좋은 자료임
    • 비슷한 방향으로 글을 쓴 적이 있음. 응용 자체라기보다는, Blind 75 문제 세트를 풀며 배운 내용으로 어떤 문제에 어떤 자료구조나 알고리즘 접근을 적용할지 고르는 가이드/의사결정 트리였음
      아직 전문가가 아니라 권위 있는 자료는 아니지만 흥미로울 수 있음: https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
    • 내 경험으로는 수업에서 이미 그렇게 함. 주어진 함수의 시간·공간 복잡도와 분석이 핵심임
    • Skiena가 이 주제로 좋은 강의를 했던 것 같음
    • 맥락과 역사를 알면 확실히 더 흥미롭고, 보통 학습에도 도움이 됨

  • 눈에 띄는 항목 하나: Marlena
    https://xlinux.nist.gov/dads/HTML/marlena.html
    이게 뭘 뜻하는지 아는 사람 있음?

  • 알고리즘을 알파벳순으로 나열한 목록이 학습자에게 좋은 출발점인지는 모르겠음
    막 시작했거나 이 주제를 확실히 익히고 싶은 사람에게는 이 고전 책이 정석이라고 봄.[1]
    개발자로 성장하고 FAANG 코딩 인터뷰를 통과하는 게 목표라면, 이것이 가장 강한 지렛대일 수도 있음
    [1] https://books.google.com/books/about/Introduction_To_Algorit...

    • 출발점으로는 아닐 가능성이 큼. 하지만 참고자료로는 훌륭함

  • 이 목록을 역방향 검색하려면 어떻게 해야 할지 궁금함
    예를 들어 어떤 알고리즘의 작동 방식은 대략 설명할 수 있지만 이름을 모르고, 이 목록에 있는지 알고 싶을 때가 있음. 요즘이라면 의사코드로 써서 ChatGPT에 주고 이름을 물어볼 수도 있겠지만, 그 외에는 잘 모르겠음

    • Discord에 가서 물어보면 누군가 알려줄 것임

  • 풀 리퀘스트를 받았으면 좋겠음. acceleration structure 같은 기본 항목이 빠져 있음

  • 정말 멋진 자료임. 예산 삭감 같은 걸 견디고 살아남았으면 좋겠고, 아카이브해둬야 함

답변달기