Tags

286 pages

C++

[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++ 백준 18438 번 : LCS 5

[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] C++ 백준 18586번 : Salty Fish

[Algorithm] C++/Python 백준 2711번 : 오타맨 고창영

백준 2711번 오타맨 고창영 문제는 주어진 문자열에서 특정 위치의 오타를 제거해 올바른 문자열로 복구하는 단순 구현 문제입니다. 입력 형식 파싱, 인덱스 조정, 문자열 처리 등을 연습할 수 있으며, 테스트 케이스마다 1-based 위치로 오타 문자를 제외한 결과 문자열을 출력해야 하는 것이 특징입니다. C++/Python의 슬라이싱, 문자열 조작 기법에 대한 이해를 향상시킬 수 있습니다.
[Algorithm] C++/Python 백준 2711번 : 오타맨 고창영