‘algorithms’ 태그의 글
3편 RSS로 구독
3편
Boyer–Moore 과반수 투표 알고리즘: 후보 하나와 카운터로 과반 찾기, 두 번째 패스가 필요한 이유
Boyer와 Moore가 1980년에 고안한 MJRTY는 후보 하나와 카운터 하나로 과반 원소 후보를 고릅니다. 동작 규칙, 정확성 논증, 과반이 없을 때 생기는 오답과 두 번째 패스를 원 논문 기준으로 정리합니다.
중앙값의 중앙값(BFPRT): 최악의 경우에도 선형 시간에 k번째 값 찾기
1973년 Blum·Floyd·Pratt·Rivest·Tarjan 논문의 PICK 알고리즘이 최악의 경우에도 선형 시간에 k번째 값을 찾는 원리와, 묶음 크기 5가 어디서 나오는지 원 논문 기준으로 정리합니다.
위상 정렬과 순환 감지: 진입 차수로 순서를 정하고 막힌 곳 찾기
의존 관계를 실행 순서로 바꾸는 위상 정렬을 진입 차수 방식으로 구현하고, 순환이 있을 때 무엇이 남는지와 Python graphlib의 TopologicalSorter·CycleError 동작을 정리합니다.
찾는 글이 없습니다. 다른 낱말로 검색해 보세요.