태그: 알고리즘
32편
-
알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기
중복 제거, 구간 합, 최단 경로, 부분합, 문자열 매칭의 TLE 코드를 복잡도 관점에서 고친 사례와 Big-O·상각 분석, 공간-시간 트레이드오프, 캐시·분기 예측까지 정리합니다.
-
C++ 캐시 교체 알고리즘: FIFO·LRU·LFU·Clock·MRU·OPT 구현과 비교
FIFO·LRU·LFU·MRU·Random·Clock·OPT 캐시 교체 정책의 동작 원리와 시간 복잡도를 비교하고, FIFO·LRU·Clock 캐시를 C++로 구현한 뒤 Redis 정책, OS 페이지 교체, CDN의 LFU 변형과 연결해 설명합니다.
-
C++ Strategy 패턴: 다형성 vs 함수 포인터 vs 람다 vs std::function으로 알고리즘 교체하기
C++ Strategy 패턴으로 알고리즘을 캡슐화하고 런타임에 교체하는 방법. 다형성, 함수 포인터, 람다, std::function 네 가지 구현과 각각의 성능 특성, 압축 알고리즘 예제를 정리합니다.
-
C++ 분할정복: 병합 정렬, 퀵소트, 이진 탐색, 가장 가까운 점 쌍, Strassen 행렬 곱
C++ 분할정복(Divide and Conquer) 패턴을 병합정렬, 퀵소트, 이진탐색, 최근접 점 쌍, Strassen 행렬 곱셈 구현으로 설명하고, 재귀 깊이·경계 조건·Combine 단계에서 생기는 버그와 병렬화 시 주의점을 다룹니다.
-
C++20 std::ranges 알고리즘: projection으로 중복 줄이기와 concept 기반 에러
C++20 std::ranges 알고리즘을 다룹니다. std::sort 대비 안전성, projection으로 코드 중복 줄이기, concept 기반 컴파일 에러, subrange 반환까지 실전 예제로 정리합니다.
-
C++로 자료구조 직접 구현하기: 연결 리스트·이진 탐색 트리·해시 테이블·스택·큐
C++로 연결 리스트, 이진 탐색 트리, 해시 테이블, 스택, 큐를 직접 구현하며 노드 연결과 삽입·삭제가 내부에서 어떻게 일어나는지 설명하고, LRU 캐시와 인접 리스트 그래프 예제로 응용합니다.
-
C++로 O(1) LRU 캐시 만들기: unordered_map + list, splice, 흔한 반복자 실수
unordered_map에 list 반복자를 저장하고 splice로 노드를 앞으로 옮겨 get과 put을 모두 O(1)로 처리하는 LRU 캐시를 C++ 템플릿으로 구현합니다. 용량 초과 시 eviction 순서와 용량 0 같은 경계 조건도 다룹니다.
-
C++ replace·replace_if·replace_copy: 값 치환과 transform 중 무엇을 쓸까
std::replace와 replace_if로 원본 범위의 값을 바꾸고, replace_copy·replace_copy_if로 원본을 유지한 채 결과를 새로 만드는 방법, std::string::replace와의 혼동, transform과의 선택 기준을 데이터 정제 예제로 설명합니다.
-
C++ reverse·rotate·reverse_copy: 범위 뒤집기와 회전 알고리즘 사용법
std::reverse로 범위를 뒤집고 reverse_copy로 원본을 유지한 채 역순 사본을 만들며, rotate로 배열을 회전하는 방법을 팰린드롬 검사, LeetCode 189 배열 회전, 151 단어 순서 뒤집기 예제로 설명합니다.
-
C++ set_union·set_intersection·set_difference: 정렬된 범위의 집합 연산
정렬된 범위에서 set_union·set_intersection·set_difference·set_symmetric_difference로 합·교·차집합을 구하고 includes로 포함 관계를 검사하는 방법을 권한 관리, 태그 필터링, 변경 사항 추적 예제로 설명합니다.
-
C++ std::copy·copy_if·copy_backward: 목적지 크기, 겹치는 범위, back_inserter
std::copy·copy_if·copy_n·copy_backward·move를 언제 골라 쓰는지 벡터 복제와 필터링 예제로 설명하고, 목적지 크기 부족, 겹치는 범위, move 후 원본 상태, back_inserter 같은 출력 반복자 선택 문제를 다룹니다.
-
C++ count·count_if와 all_of·any_of·none_of로 조건 집계하기
std::count로 특정 값의 개수를 세고 count_if에 람다를 넘겨 조건별로 집계하는 방법, 구조체 필드 기준 카운트, all_of·any_of·none_of로 조건을 검사하는 법을 통계 유틸리티 예제와 함께 설명합니다.
-
C++ fill·generate·iota로 범위 채우기: 테스트 데이터 생성 예제
std::fill과 fill_n으로 범위를 같은 값으로 채우고, generate에 람다나 함수 객체를 넘겨 난수·ID·구조체 데이터를 만들며, iota로 연속 값을 생성하는 방법을 테스트 데이터 생성기 예제와 함께 설명합니다.
-
C++ make_heap·push_heap·pop_heap: priority_queue 대신 힙을 직접 다룰 때
std::make_heap·push_heap·pop_heap·sort_heap으로 벡터를 직접 힙으로 관리하는 방법, 최대 힙과 최소 힙을 만드는 비교자, priority_queue와 비교한 장단점, Top-K 추출과 힙 정렬 구현을 예제로 설명합니다.
-
C++ min·max·minmax_element와 std::clamp: 값 비교와 범위 제한
두 값 비교용 std::min·max·minmax와 범위용 min_element·max_element·minmax_element의 차이, 커스텀 비교자, C++17 std::clamp로 마우스 좌표를 화면 안으로 제한하는 예제와 통계·정규화 패턴을 다룹니다.
-
C++ <numeric> 알고리즘: accumulate·reduce·scan의 차이와 함정
<numeric>의 accumulate와 C++17 reduce·transform_reduce의 차이, inner_product, partial_sum과 inclusive·exclusive_scan, adjacent_difference, iota를 통계·복리 이자·이동 평균 계산 예제로 설명합니다.
-
C++ partition·stable_partition·partition_point: 조건으로 범위 나누기
std::partition으로 조건에 맞는 요소를 앞쪽으로 모으고, 상대 순서를 지키는 stable_partition과 비교하며, 분할된 범위에서 partition_point로 경계를 이진 탐색하는 방법과 3-way 분할, 퀵 정렬 한 단계 스케치를 다룹니다.
-
C++ next_permutation으로 순열·조합 만들기: 정렬 후 do-while 패턴
next_permutation과 prev_permutation으로 사전순 순열을 만드는 방법을 설명하고, 정렬부터 하고 do-while로 돌리는 패턴, 문자열 순열, n개 중 k개 순열과 조합 생성, 완전 탐색에 적용하는 예제를 다룹니다.
-
C++ 알고리즘 문제풀이 | 코딩테스트 필수 문제 10선
Two Sum, 이진 탐색, 최대 부분 배열 합, 동전 거스름돈, 섬의 개수, 유효한 괄호, LIS, 0/1 배낭, 다익스트라, 순열·조합까지 코딩테스트 단골 10문제를 C++ STL 풀이와 시간복잡도 분석으로 풀어 봅니다.
-
C++ remove·remove_if가 원소를 지우지 않는 이유: erase-remove와 C++20 erase_if
std::remove와 remove_if가 실제로 요소를 지우지 않고 뒤로 밀어 내기만 하는 이유를 설명하고, erase-remove 관용구, 정렬 후 unique로 중복 제거하는 방법, C++20 std::erase·erase_if로 간결하게 쓰는 법을 다룹니다.
-
C++ 알고리즘 최적화: Big-O로 병목 찾기, 공간-시간 트레이드오프, 메모이제이션
데이터가 늘자 응답이 느려질 때 Big-O로 병목을 찾고, 메모이제이션·해시 테이블로 메모리를 내주고 시간을 줄이거나 롤링 배열로 DP 공간을 줄이는 방법을 C++ 예제로 봅니다. Kadane, 투 포인터, partial_sort와 nth_element 비교도 포함합니다.
-
C++ 문자열 패턴 매칭: KMP, Rabin-Karp, Boyer-Moore, Z 알고리즘, 접미사 배열
대용량 로그 검색, 표절 검사, 에디터 찾기 기능처럼 상황에 따라 KMP, Rabin-Karp, Boyer-Moore, Z 알고리즘, 접미사 배열 중 무엇을 쓸지 고르고 C++로 구현합니다. LPS 실패 함수 구축과 해시 충돌 처리도 다룹니다.
-
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++로 구현하고 DP가 필요한 경우와 비교합니다.
-
C++ 수학 알고리즘: 에라토스테네스의 체, 유클리드 GCD, 모듈러 거듭제곱, 행렬, FFT
기약분수 계산의 오버플로, 느린 소수 판별, 거듭제곱 mod 시간 초과 같은 문제를 유클리드 GCD, 에라토스테네스의 체, 빠른 거듭제곱, 확장 유클리드·페르마 모듈러 역원, 행렬 거듭제곱으로 해결하는 C++ 코드를 봅니다.
-
상황별 C++ 알고리즘 고르기: STL로 충분한 경우와 직접 구현할 때, 흔한 성능 함정
로그 검색, 중복 제거, Top-K 추출, 정렬된 범위의 구간 검색 같은 상황마다 어떤 STL 알고리즘이 맞는지 고르는 기준입니다. binary_search 전제 위반, remove 후 erase 누락, 비교자 약순서 위반 같은 흔한 실수도 짚습니다.
-
C++ 그래프 알고리즘: BFS·DFS, 다익스트라, Kruskal·Prim 최소신장트리, Union-Find
지도 최단 경로, 친구의 친구 탐색, 빌드 의존성 순서, 최소 비용 배선 같은 문제에 맞춰 BFS·DFS, 위상 정렬, 다익스트라, Kruskal·Prim, Union-Find를 C++로 구현합니다. 음수 간선에서 다익스트라가 틀리는 이유도 설명합니다.
-
C++ 동적 계획법: 메모이제이션 vs 타뷸레이션, 2D→1D 공간 최적화, 배낭·LCS·Bitmask DP
fib(40)이 느린 이유에서 출발해 메모이제이션과 타뷸레이션의 차이, 2D 테이블을 1D rolling array로 줄이는 방법을 설명합니다. 0/1 배낭, LCS, LIS, 편집 거리, Bitmask DP를 C++로 풀고 재귀 스택 오버플로를 피하는 법도 봅니다.
-
C++ STL 알고리즘 기초: sort·find·transform·accumulate 실전 활용
for문으로 직접 짠 정렬·검색·집계에서 버그가 나는 상황을 std::sort, find_if, count_if, transform, accumulate로 바꾸는 방법을 보여줍니다. remove 후 erase 누락, accumulate 초기값 실수, 비교자 규칙 위반도 짚습니다.
-
C++ STL 고급 알고리즘: partition·merge·집합 연산·힙 연산 쓰는 법과 흔한 실수
partition과 stable_partition으로 조건 분할하기, 정렬된 두 범위를 merge와 set_union·set_intersection으로 합치고 교집합 구하기, make_heap·push_heap으로 우선순위 큐를 직접 다루는 법을 예제로 정리하고, 정렬되지 않은 입력을 넘기는 실수 같은 함정을 짚습니다.
-
C++ 코딩 테스트 준비: 백준·프로그래머스 유형별 STL 활용과 입출력 최적화
백준과 프로그래머스에서 자주 나오는 정렬, 해시, 투 포인터, DP, BFS/DFS, 그리디, 백트래킹 문제를 C++ STL로 푸는 방법을 유형별로 정리하고, 입력 크기로 허용 복잡도를 가늠하는 법과 cin 입출력 최적화를 다룹니다.