태그: 알고리즘
59편
-
배열과 연결 리스트: 메모리 구조, 연산별 시간 복잡도, 코딩 테스트 활용
배열과 연결 리스트가 메모리에 놓이는 방식 때문에 인덱스 접근, 중간 삽입·삭제의 비용이 어떻게 달라지는지 설명하고, 투 포인터·슬라이딩 윈도우로 배열 회전, 중복 제거, k번째 큰 수 같은 문제를 Python과 C++로 풉니다.
-
트리 자료구조: 이진 트리, 이진 탐색 트리(BST), 전위·중위·후위 순회
루트·자식·높이 같은 트리 용어부터 전위·중위·후위·레벨 순회, 이진 탐색 트리의 삽입과 검색까지 Python으로 구현하고, 트리 높이, 대칭 트리, 최소 공통 조상(LCA) 문제를 재귀로 푸는 방법을 보여 줍니다.
-
코딩 테스트 준비 전략: 알고리즘 학습 순서와 시험장 실전 팁
투 포인터·슬라이딩 윈도우·이진 탐색·그래프 탐색부터 DP·그리디·최단경로·위상정렬·트라이까지 개념과 실수 포인트를 풀어 쓰고, 자료구조·패턴·시간 배분·언어 선택으로 이어지는 코딩 테스트 준비 글입니다.
-
AVL 트리 구현: 균형 인수, LL·RR·LR·RL 회전, 삽입과 Red-Black 트리 비교
정렬된 값을 차례로 넣으면 일반 이진 탐색 트리가 한쪽으로 기울어 O(n)이 되는 문제를 AVL 트리가 균형 인수와 회전으로 해결하는 과정을 보여줍니다. LL·RR·LR·RL 회전, 삽입 구현 코드, Red-Black 트리와의 비교를 다룹니다.
-
LeetCode 패턴: 두 포인터와 슬라이딩 윈도우 | 템플릿과 C++/Python
Minimum Window Substring, 3Sum, Container With Most Water 등 14개 LeetCode 문제로 두 포인터와 고정·가변 슬라이딩 윈도우 템플릿을 익히고, 이중 while이 O(n)인 이유와 단조성이 깨지면 패턴을 쓰면 안 되는 이유를 설명합니다.
-
코딩 테스트에서 시간 복잡도 줄이는 체크리스트 | TLE 탈출
코딩 테스트에서 시간 초과(TLE)가 났을 때 모든 쌍을 보는 중첩 루프, 반복되는 구간 합 계산, 선형 탐색, 쿼리마다 전체 순회를 차례로 점검해 누적 합·해시·세그먼트 트리·펜윅 트리로 바꾸는 5단계 체크리스트를 제공합니다.
-
알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기
TLE 사례, Big-O 정의·증명 스케치, 상각분석, 공간-시간 트레이드오프 예제, 캐시·분기예측, 프로덕션 패턴까지 알고리즘 최적화 총정리. 코딩테스트 합격과 실무 성능 개선을 동시에 해결하는 실전 가이드.
-
BFS vs DFS: 동작 방식·복잡도 비교와 문제 유형별 선택 기준
BFS는 큐로 층별로 퍼지고 DFS는 스택·재귀로 한 갈래를 끝까지 파고듭니다. 두 방식의 시간·공간 복잡도 차이와 최단 경로, 사이클 탐지, 연결 요소 문제에서 무엇을 골라야 하는지를 미로 탈출·섬의 개수 예제로 비교합니다.
-
이진 탐색: 경계 조건, lower/upper bound, 결정 문제로 바꾸는 파라메트릭 서치
정렬된 배열에서 절반씩 범위를 줄이는 이진 탐색을 반복·재귀로 구현하고, lower bound와 upper bound로 원소 개수를 세는 법, 나무 자르기처럼 답을 직접 찾는 대신 결정 문제로 바꿔 푸는 파라메트릭 서치를 설명합니다.
-
BFS와 DFS: 큐·재귀로 구현하는 그래프 탐색과 최단 거리·연결 요소 문제
BFS는 큐로, DFS는 재귀와 스택으로 구현하면서 BFS로 가중치 없는 그래프의 최단 거리를 구하는 방법과 DFS로 연결 요소를 세는 방법을 미로 탈출·섬의 개수 문제로 익힙니다. Python 재귀 한도 문제도 다룹니다.
-
백트래킹: 가지치기로 모든 경우의 수를 줄이는 방법과 N-Queen·순열·조합
백트래킹 알고리즘의 핵심 패턴(선택-재귀-되돌리기)을 순열·조합·부분집합·N-Queen·스도쿠 예제로 정리합니다. 되돌리기 누락, 가지치기 누락, 중복 결과 같은 자주 겪는 실수와 해결법도 함께 다룹니다.
-
동적 프로그래밍(DP): 메모이제이션과 타뷸레이션, 점화식 세우는 법
피보나치 수열로 중복 계산 문제를 확인한 뒤, 메모이제이션(Top-Down)과 타뷸레이션(Bottom-Up)으로 같은 문제를 풀어 보고 1차원·2차원 DP와 배낭 문제에서 상태 정의, 점화식, 초기값을 세우는 순서를 설명합니다.
-
DP 패턴 정리: 1차원·2차원 DP, 배낭 문제, LIS 점화식 세우는 법
계단 오르기 같은 1차원 DP, 격자 경로와 LCS 같은 2차원 DP, 0-1 배낭과 무한 배낭, LIS의 O(n²)·O(n log n) 풀이까지 자주 나오는 DP 유형을 점화식과 Python 코드로 비교합니다.
-
DP 실전 문제 풀이: 1로 만들기·편집 거리·동전·LIS·배낭으로 점화식 연습
1로 만들기, 편집 거리, 동전 문제, LIS, 배낭 문제를 Bottom-Up과 Top-Down으로 직접 풀면서 상태 정의와 점화식 세우는 연습을 하고, 동전 문제에서 최소 개수뿐 아니라 사용한 동전까지 역추적하는 방법도 보여 줍니다.
-
그리디 알고리즘: 매 순간 최선을 선택하는 이유와 한계
그리디 알고리즘의 정당성 증명과 반례 찾기, 활동 선택·배낭 문제·최소 신장 트리 등 필수 유형을 실전 예제로 정리. 교환 논법(Exchange Argument)부터 프로그래머스·백준 문제까지 단계별로 학습.
-
투 포인터: O(n²) 탐색을 O(n)으로 줄이는 조건과 대표 문제
양 끝에서 좁혀 오는 방식과 같은 방향으로 함께 움직이는 방식, 두 가지 투 포인터 패턴으로 세 수의 합, 컨테이너 물 담기, 부분 배열 합 문제를 풀며 이중 루프를 O(n)으로 줄이는 조건을 설명합니다.
-
슬라이딩 윈도우로 부분 배열 문제 최적화하기
슬라이딩 윈도우는 연속 구간을 O(n)으로 다루는 기법입니다. 고정·가변 예제, 같은 방향 다중 포인터, 모노토닉 덱, 상각 분석, 관측·스트림 실무 패턴을 정리합니다. 연속 부분 배열이나 부분 문자열의 합·조건을 매번 처음부터 다시 계산하면 시간 초과가 나기 쉽습니다. 이 글에서는 윈도우를 한 칸씩 밀며 갱신하는 방식으로 복잡도를 줄이는 흐름을 단계적으로 익힐 수 있습니다.
-
스택과 큐: LIFO·FIFO 구현과 괄호 검사·BFS 같은 코딩 테스트 활용
스택(LIFO)과 큐(FIFO)를 Python list·deque와 C++ STL로 구현해 보고, 괄호 검사, 스택 두 개로 큐 만들기, 다음 큰 수, BFS 문제를 풀면서 list.pop(0)이 느린 이유와 C++ pop()이 값을 반환하지 않는 이유도 짚습니다.
-
해시 테이블: O(1) 탐색 원리, 충돌 처리, 코딩 테스트 활용 패턴
해시 함수와 체이닝·개방 주소법 충돌 처리, 부하율 관리가 평균 O(1) 탐색을 만드는 원리를 설명하고, Python dict·Counter·defaultdict로 Two Sum, 완주하지 못한 선수, 베스트앨범, 그룹 애너그램 문제를 풉니다.
-
그래프 자료구조: 인접 리스트와 인접 행렬, 그래프 탐색 기초
인접 리스트와 인접 행렬의 메모리·탐색 비용 차이를 비교하고, BFS·DFS로 연결 요소 개수, 사이클 감지, 위상 정렬을 구현합니다. 친구 추천, 작업 의존성 해결, 미로 최단 경로 같은 실제 적용 예도 함께 다룹니다.
-
기초 정렬 알고리즘: 버블·선택·삽입 정렬의 동작과 O(n²)인 이유
버블·선택·삽입 정렬을 Python과 C++로 구현하며 세 알고리즘이 모두 O(n²)인 이유와 안정성 차이를 비교하고, 거의 정렬된 데이터나 작은 배열에서 삽입 정렬이 지금도 실제로 쓰이는 이유를 설명합니다.
-
고급 정렬: 퀵·병합·힙 정렬이 O(n log n)인 이유와 선택 기준
퀵·병합·힙 정렬이 O(n log n)이 되는 분할 방식을 Python과 C++ 구현으로 설명하고, 퀵 정렬 최악 O(n²)을 피하는 피벗 선택, 병합 정렬의 추가 메모리, 안정성 요구에 따라 알고리즘을 고르는 기준을 비교합니다.
-
정렬 문제 풀이: 커스텀 비교 함수, 안정 정렬, 코딩 테스트 정렬 패턴
코딩 테스트 정렬 문제 풀이, 커스텀 key, 퀵·머지·힙·카운팅 정렬의 내부 동작과 프로덕션 정렬 패턴까지 정리합니다. 코딩 테스트에서 정렬은 문제 해결의 첫 단계인 경우가 많습니다. 후보를 점수·시간 순으로 줄이거나, 그리디·이진 탐색 전에 순서를 맞출 때 sort와 key만으로 조건을 표현하는 경우가 많습니다.
-
C++ 캐시 교체 알고리즘: FIFO·LRU·LFU·Clock·MRU·OPT 구현과 비교
FIFO·LRU·LFU·MRU·Random·Clock·OPT 캐시 교체 정책의 동작 원리와 시간 복잡도를 비교하고, FIFO·LRU·Clock 캐시를 C++로 구현한 뒤 Redis 정책, OS 페이지 교체, CDN의 LFU 변형과 연결해 설명합니다.
-
알고리즘 시리즈 목차 | 자료구조부터 DP·그리디까지 코딩 테스트 학습 순서
배열·스택·해시 테이블 같은 자료구조부터 정렬, 이진 탐색, BFS/DFS, DP, 그리디, 투 포인터, 슬라이딩 윈도우까지 알고리즘 시리즈 17편을 난이도 순으로 묶고, 입문·중급·집중 대비별 학습 경로를 제시합니다.
-
C++ STL 알고리즘 자주 쓰는 함수 20개: sort·lower_bound·accumulate·remove_if
C++ STL <algorithm>에서 자주 쓰는 함수 20개(sort, find, lower_bound, accumulate, transform, remove_if 등) 예제 정리. erase-remove 관용구와 binary_search 전제 조건 같은 실수도 다룹니다.
-
C++ Strategy 패턴: 다형성 vs 함수 포인터 vs 람다 vs std::function으로 알고리즘 교체하기
C++ Strategy 패턴으로 알고리즘을 캡슐화하고 런타임에 교체하는 방법. 다형성, 함수 포인터, 람다, std::function 네 가지 구현 비교, 압축 알고리즘 예제와 성능 비교를 정리합니다.
-
STL 알고리즘 기본기: sort·find·count·transform·accumulate·copy·remove와 Ranges
C++ STL 알고리즘 정리. sort, find, count, transform, accumulate, copy, remove-erase 관용구 같은 기본 알고리즘과 C++20 Ranges·프로젝션, C++23 views, 자주 나는 에러를 예제로 다룹니다.
-
C++ 분할정복: 병합 정렬, 퀵소트, 이진 탐색, 가장 가까운 점 쌍, Strassen 행렬 곱
C++ 분할정복(Divide and Conquer) 패턴: 병합정렬, 퀵소트, 이진탐색, 최근접 점 쌍, Strassen 행렬 곱셈. 문제 시나리오, 완전한 예제, 흔한 실수, 베스트 프랙티스, 프로덕션 패턴.
-
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++ find·binary_search·lower_bound: 정렬 전제가 깨질 때 생기는 조용한 오류
C++ find, binary_search, lower_bound 등 STL 검색. 정렬 안 된 범위에서 binary_search를 쓰면 왜 조용히 틀린 결과가 나오는지, 비교자 불일치 함정까지 실전 코드로 설명합니다.
-
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++ Algorithm Numeric | accumulate·reduce
<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로 병목을 찾고, 메모이제이션·슬라이딩 윈도우·해시 테이블로 공간을 내주고 시간을 줄이는 방법을 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 같은 기수 기반 정렬, 자주 나는 에러와 성능 팁을 다룹니다.
-
STL 정렬과 검색 함께 쓰기: sort·stable_sort·병렬 정렬과 lower_bound·upper_bound
C++ STL 정렬·검색 정리. std::sort(introsort 계열), stable_sort, std::execution::par 병렬 정렬, lower_bound·upper_bound 이진 탐색, 자주 나는 에러와 성능 팁을 예제로 다룹니다.
-
알고리즘에서 쓰는 비트 연산: 비트마스크 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 입출력 최적화를 다룹니다.