태그: 알고리즘
22편
-
알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(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++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++ 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 입출력 최적화를 다룹니다.