[Algorithm] C++ 백준 18438 번 : LCS 5

백준 18438 LCS 5는 최대 7000 길이의 두 문자열에 대해 LCS의 길이와 실제 수열을 모두 출력해야 하는 문제입니다. 4MB 메모리 제한 때문에 전형적인 2차원 DP 테이블을 저장할 수 없으므로, O(nm) 시간에 O(min(n,m)) 메모리만 사용하는 Hirschberg 알고리즘으로 안전하게 복원합니다. 전방·후방 1차원 DP, 분할 지점 선택, 경계 처리와 빠른 입출력까지 반영한 C++ 구현과 복잡도 분석을 제공합니다.

[Algorithm] C++ 백준 18473번 : Fast Spanning Tree

BOJ 18473 Fast Spanning Tree는 인덱스가 작은 간선부터 조건을 만족할 때만 연결하는 과정을 효율적으로 복원하는 문제입니다. DSU(Union-Find)와 small-to-large 병합, 부족분 절반 기준의 watcher, 전역 후보 우선순위 큐를 이용해 O(m log m) 내에 기록된 간선 인덱스 시퀀스를 재현하는 C++ 구현과 핵심 아이디어를 정리했습니다.

[Algorithm] C++ 백준 18586번 : Salty Fish

트리의 각 노드 사과를 모두 먹되, 카메라가 보는 구간(p(x,k))의 변화를 막기 위해 일부 카메라를 매수(비용 c)하거나 일부 정점을 포기하는 문제를 최소 컷으로 환원한다. 거대한 일반 네트워크 대신 트리 구조를 활용해 dp(map<depth,sum>)을 small-to-large로 병합하고, 카메라별 커버 가능한 가장 깊은 depth부터 잔여 유량을 소모해 Max-Flow=Min-Cut을 암시적으로 계산, 전체 사과 합 − 유량으로 최대 수익을 구한다. 시간복잡도는 O((n+m) log n)으로 테스트케이스 합 n,m ≤ 10^6에서도 빠르게 동작한다.

Algorithm BOJ JOI

[Algorithm] C++ 백준 18855번 : Treatment Project

JOI 2019/2020 Day4 C, 백준 18855 Treatment Project의 정해 구현. 프로젝트들을 정점(정점 비용)으로 보고 시간-구간 제약을 불등식으로 변환해 간선을 정의, 시작(L=1)에서 종료(R=N)까지 정점 비용 최단경로를 다익스트라로 구한다. 간선 전개는 T별로 정렬해 세그트리로 한 번씩만 활성화하여 전체 O(M log M)에 해결한다.

[Algorithm] C++ 백준 31403번 : A + B - C

백준 31403 A + B - C 문제를 Python과 C++로 풀이합니다. 숫자로 계산하는 A + B - C와 문자열을 이어붙인 뒤 int로 변환하여 C를 빼는 연산의 차이를 예제와 함께 설명하고, 빠른 입출력 코드, 복잡도, 테스트 팁까지 간결하게 정리했습니다.

[Algorithm] C++ 백준 3419번 : Racing Car Trail

백준 3419 Racing Car Trail을 격자 그래프의 이분 그래프로 모델링해 Hopcroft–Karp 최대 매칭과 Dulmage–Mendelsohn 도달성으로 각 시작 칸의 승패(A/B)를 판정합니다. O(E√V) 매칭과 O(V+E) 마킹으로 빠르게 처리하며, 구현 디테일과 복잡도까지 정리.

[Algorithm] C++ 백준 3444번 : Robotic Sort

백준 3444 Robotic Sort는 로봇 팔이 연속 구간을 뒤집는 연산만으로 샘플을 안정적으로 오름차순 정렬하도록 P1..PN을 출력하는 문제입니다. Implicit Treap로 현재 위치 계산과 구간 뒤집기를 O(N log N)으로 처리한 C++ 풀이.

[Algorithm] C++ 백준 3527번 : Jungle Outpost

BOJ 3527 Jungle Outpost 문제를 반평면 교집합(HPI)과 이분탐색으로 해결. k개의 연속 정점 제거에도 항상 보호되는 HQ가 존재하는지 공집합 여부로 판정하고, 가장 큰 k를 찾아 k+1을 정답으로 출력하는 실전 C++ 구현과 핵심 아이디어 정리.

[Algorithm] C++ 백준 7907번 : Bytean Road Race

Bytean Road Race(백준 7907)을 동/남 방향 격자 DAG로 모델링해 두 정점 p, q를 모두 지나는 경로 존재 여부를 O(1)로 판별하는 C++ 풀이. 동우선·남우선 위상정렬 두 랭크 비교와 O(N+M) 전처리로 빠르고 안정적인 질의 응답을 제공합니다.

[Algorithm] C++ 백준 8235번 : Prefixuffix

백준 8235 Prefixuffix는 접두사와 접미사의 회전 동치 최대 길이를 구하는 문자열 문제입니다. 두 포인터와 롤링 해시(모듈러)로 T=A+B+X+B+A 구조를 O(n)에 찾아 C++로 구현하고, 경계 처리와 충돌 안정성까지 설명합니다.