‘알고리즘’ 태그의 글
20편 RSS로 구독
20편
Project Euler 5: 1부터 20까지 모두로 나누어떨어지는 가장 작은 수를 최소공배수로 바로 만들기
1부터 20까지의 모든 수로 나누어떨어지는 가장 작은 양의 정수를, 하나씩 찾아보는 대신 유클리드 호제법과 lcm(a, b) = a / gcd(a, b) × b를 거듭 적용해 만듭니다. 이 방법이 왜 정확히 최소공배수를 주는지 증명하고, 정수 범위와 C++17·Python 3 구현까지 다룹니다.
Jump Consistent Hash: 표 없이 샤드 번호를 정하는 일관된 해시와 그 전제 조건
샤드를 10개에서 12개로 늘릴 때 hash mod n은 키의 5/6을 옮기지만 꼭 옮겨야 하는 건 1/6입니다. Lamping·Veach 논문의 Jump Consistent Hash 코드, 동작 원리, 버킷을 늘리고 줄일 때 생기는 일을 정리했습니다.
Project Euler 4: 세 자리 수 두 개의 곱에서 가장 큰 회문수를 위에서부터 찾기
두 세 자리 수의 곱 중 가장 큰 회문수를 큰 곱부터 탐색하고 가지치기해서 구합니다. 가지치기가 왜 답을 놓치지 않는지 증명하고, 짝수 자리 회문수와 11의 관계, 정수 범위, C++17과 Python 3 구현까지 다룹니다.
유니온 파인드의 경로 압축과 크기 가중치: α(n)은 어떤 구현에 붙는 숫자인가
유니온 파인드에서 크기 가중치, 경로 압축, 경로 절반이 parent 배열을 각각 어떻게 바꾸는지 작은 예로 따라가고, 최악 Θ(log n)과 연산 열 전체의 O(m α(n))이 어느 구현에 해당하는지 Princeton algs4 자료를 기준으로 정리했습니다.
Project Euler 3: 나눌 수 있는 만큼 나눠서 가장 큰 소인수 찾기
작은 수부터 나눌 수 있는 만큼 나누는 시행 나눗셈으로 12자리 정수의 가장 큰 소인수를 구합니다. 남은 값이 왜 소수인지 증명하고, √n 반복 상한과 64비트 정수 범위, C++17과 Python 3 구현까지 다룹니다.
KMP 실패 함수: 불일치가 나면 패턴은 어디로 돌아가나
KMP 문자열 검색에서 불일치 뒤 패턴의 어느 위치를 다시 비교할지 정하는 f·next 표의 정의와 계산법, 전체가 선형 시간이 되는 이유를 1977년 원 논문과 Princeton 구현으로 정리합니다.
Project Euler 2: 짝수 피보나치 수만 골라 더하기
피보나치 수열에서 짝수 항이 세 칸마다 나온다는 사실을 증명하고, 짝수 항끼리의 점화식 E(k) = 4E(k−1) + E(k−2)를 유도해 사백만 이하의 짝수 항만 더합니다. C++17과 Python 3 구현, 정확성 증명, 정수 범위까지 다룹니다.
Project Euler 1: 3 또는 5의 배수의 합을 O(1)로
1000 미만에서 3이나 5로 나누어떨어지는 수의 합을, 반복문 대신 포함-배제와 등차수열의 합으로 구합니다. C++17과 Python 3 구현, 정확성 증명, 정수 범위까지 다룹니다.
Linux 커널 rbtree: 비교 함수를 저장하지 않고 노드를 구조체에 넣어 쓰는 레드-블랙 트리
Linux의 레드-블랙 트리는 비교 함수를 저장하지 않습니다. 노드를 구조체에 넣는 방식, 직접 쓰는 검색·삽입 루프와 호출마다 비교 함수를 받는 도우미, 색 비트, cached·augmented 트리, 락 없는 조회의 한계를 v6.17 소스로 정리했습니다.
스킵 리스트: 동전 던지기로 정한 레벨이 O(log n) 검색을 만드는 방식
정렬된 연결 리스트에 무작위 레벨의 포인터를 더하면 검색이 왜 기대 O(log n)이 될까요? Pugh의 보고서에 실린 알고리즘, '기대' 시간의 범위, Java ConcurrentSkipListMap 문서가 약속하는 것을 정리했습니다.
길이를 모르는 스트림에서 k개를 고르게 뽑기: 저수지 샘플링(Algorithm R)
전체 개수를 모르는 데이터를 한 번만 읽으면서 k개를 무작위로 뽑는 저수지 샘플링. 교체 확률이 왜 k/i인지, 모든 원소가 k/n으로 남는 증명, k개 조합 전체가 고른지, 흔한 범위 실수까지 정리했습니다.
해시 테이블은 언제 O(1)이 아닐까: 충돌, O(n²) 삽입, 해시 플러딩
dict와 HashMap의 O(1)은 기댓값입니다. 키의 해시가 모두 같으면 n개 삽입에 비교가 최소 n(n−1)/2번 필요한 이유, Python 해시 무작위화와 PYTHONHASHSEED, Rust SipHash, Java의 Comparable 대응을 정리했습니다.
블룸 필터가 '없음'만 확신하는 이유
블룸 필터가 '확실히 없음'과 '있을 수도 있음'으로만 답하는 이유, 거짓 음성이 없다는 보장이 성립하는 조건, 거짓 양성 확률 식, 비트를 지우면 보장이 깨지는 이유를 정리합니다.
sort(() => Math.random() - 0.5)로 섞으면 안 되는 이유: Fisher–Yates 셔플
랜덤 비교 함수로 배열을 섞으면 왜 고르게 섞이지 않는지 ECMAScript 명세로 확인하고, 모든 순열이 같은 확률로 나오는 Fisher–Yates 셔플과 난수 범위·생성기 주의점을 정리했습니다.
퀵 정렬은 언제 O(n²)이 될까: 표준 정렬이 최악을 막는 방법
정렬된 입력, median-of-3 killer, 적대적 비교 함수처럼 퀵 정렬을 이차 시간으로 만드는 경우와 introsort의 깊이 제한, C++·Rust·Go·Java 문서가 보장하는 범위를 정리합니다.
다익스트라 알고리즘에 음수 가중치를 넣으면 왜 틀릴까
다익스트라의 탐욕적 선택이 음수 간선에서 깨지는 이유를 간선 세 개짜리 반례로 확인하고, 벨만–포드와 DAG 최단 경로를 언제 쓰는지 정리합니다.
힙은 정렬된 배열이 아니다: 우선순위 큐의 배열 순서와 인덱스 공식
heapq나 PriorityQueue를 출력하면 왜 정렬되어 있지 않을까요? 힙이 지키는 조건과 0부터 세는 부모·자식 인덱스 공식, 정렬된 리스트와의 비용 차이, 같은 우선순위 처리를 공식 문서로 정리했습니다.
이진 탐색의 삽입 위치: bisect, lower_bound, binarySearch는 무엇을 돌려주나
값이 없거나 중복될 때 Python bisect, C++ lower_bound, Java Arrays.binarySearch가 돌려주는 위치와 각 API의 전제 조건을 공식 문서와 C++ 표준을 따라 비교했습니다.
배열 끝에 추가하는 append는 왜 O(1)일까: 동적 배열과 상각 시간
가끔 배열 전체를 복사하는데도 append가 O(1)인 이유를 용량과 상각 분석으로 설명하고, Java·C++·Rust·Go 문서가 보장하는 범위와 구현이 정하는 증가율, 용량을 미리 잡는 방법을 정리했습니다.
안정 정렬(stable sort)이란: 같은 값의 순서가 지켜지는 정렬
안정 정렬의 뜻, 여러 기준으로 정렬할 때 왜 중요한지, Python·JavaScript·Java·C++ 표준 정렬이 무엇을 보장하는지 명세와 공식 문서를 기준으로 정리했습니다.
찾는 글이 없습니다. 다른 낱말로 검색해 보세요.