블로그
-
C++ 문자열 패턴 매칭: KMP, Rabin-Karp, Boyer-Moore, Z 알고리즘, 접미사 배열
대용량 로그 검색, 표절 검사, 에디터 찾기 기능처럼 상황에 따라 KMP, Rabin-Karp, Boyer-Moore, Z 알고리즘, 접미사 배열 중 무엇을 쓸지 고르고 C++로 구현합니다. LPS 실패 함수 구축과 해시 충돌 처리도 다룹니다.
-
구간 쿼리와 누적합을 위한 트리: 세그먼트 트리, 펜윅 트리, 트라이 구현
구간 합 쿼리가 O(n)이라 느릴 때 쓰는 세그먼트 트리(구간 합·RMQ), 누적합 갱신에 강한 펜윅 트리, 자동완성용 트라이를 C++로 구현합니다. 펜윅과 세그먼트 트리를 언제 골라야 하는지도 비교합니다.
-
C++ 정렬 알고리즘 구현과 비교: std::sort의 pdqsort, stable_sort, 병렬 정렬, 기수 정렬
C++ 정렬 알고리즘 정리. 기본·고급 정렬 구현, std::sort 내부의 pdqsort와 stable_sort의 차이, std::execution::par 병렬 정렬, ska_sort 같은 기수 기반 정렬, 자주 나는 에러와 성능 팁을 다룹니다.
-
알고리즘에서 쓰는 비트 연산: 비트마스크 DP, XOR 트릭, 비트 카운팅, 해밍 거리, bitset
부분집합 열거, 홀수 번 등장하는 원소 찾기, 해밍 거리, TSP 상태 압축, 권한 플래그를 비트 연산으로 푸는 C++ 예제입니다. 부호 있는 시프트와 시프트 범위 초과, 연산자 우선순위 실수, C++20 <bit> 헤더 활용도 다룹니다.
-
C++ 분할정복: 병합 정렬, 퀵소트, 이진 탐색, 가장 가까운 점 쌍, Strassen 행렬 곱
C++ 분할정복(Divide and Conquer) 패턴을 병합정렬, 퀵소트, 이진탐색, 최근접 점 쌍, Strassen 행렬 곱셈 구현으로 설명하고, 재귀 깊이·경계 조건·Combine 단계에서 생기는 버그와 병렬화 시 주의점을 다룹니다.
-
탐욕 알고리즘이 맞는지 증명하기: 교환 논증과 활동 선택·거스름돈·작업 스케줄링 예제
매 순간 최선을 고르는 탐욕법이 언제 최적해를 보장하는지 교환 논증으로 확인하는 방법입니다. 활동 선택, 분수 배낭, 거스름돈, 지연 최소화 스케줄링, 회의실 배정, 허프만 코딩을 C++로 구현하고 DP가 필요한 경우와 비교합니다.
-
C++ 수학 알고리즘: 에라토스테네스의 체, 유클리드 GCD, 모듈러 거듭제곱, 행렬, FFT
기약분수 계산의 오버플로, 느린 소수 판별, 거듭제곱 mod 시간 초과 같은 문제를 유클리드 GCD, 에라토스테네스의 체, 빠른 거듭제곱, 확장 유클리드·페르마 모듈러 역원, 행렬 거듭제곱으로 해결하는 C++ 코드를 봅니다.
-
C++ 알고리즘 최적화: Big-O로 병목 찾기, 공간-시간 트레이드오프, 메모이제이션
데이터가 늘자 응답이 느려질 때 Big-O로 병목을 찾고, 메모이제이션·해시 테이블로 메모리를 내주고 시간을 줄이거나 롤링 배열로 DP 공간을 줄이는 방법을 C++ 예제로 봅니다. Kadane, 투 포인터, partial_sort와 nth_element 비교도 포함합니다.
-
C++ 플러그인 시스템 만들기: dlopen·LoadLibrary, C ABI 인터페이스, 핫 리로드
앱을 다시 빌드하지 않고 기능을 추가하는 C++ 플러그인 시스템을 만듭니다. dlopen·LoadLibrary 추상화, extern "C" 인터페이스로 ABI 불일치를 막는 법, 버전을 확인하는 플러그인 매니저, 파일 변경 감지 핫 리로드와 그 함정을 다룹니다.
-
C++ 리플렉션 구현 | 타입 정보·메타데이터·자동 직렬화
구조체마다 to_json·from_json을 손으로 짜는 대신 타입 레지스트리로 멤버 메타데이터를 등록해 직렬화와 설정 로딩을 자동화하는 C++ 리플렉션 구현입니다. 매크로로 반복을 줄이는 법, RTTR 라이브러리, 중복 등록 같은 함정도 다룹니다.