Tags

199 pages

Implementation

[Algorithm] C++ 백준 17955번 Max or Min

원형 배열에서 한 칸을 골라 인접 세 수의 최소/최대로 바꾸는 연산으로 모든 값을 x로 만드는 최소 시간을 구한다. 배열에 x가 없으면 불가능(-1). 인접 쌍마다 (min+1..max-1)에 1을 더하는 차분 누적으로 ‘그룹 수’를 집계하고, 시작점을 한 칸 회전한 두 번의 집계를 취해 중복을 보정한다. 정답은 (n - cnt[x]) + max(groups1[x], groups2[x])로 계산한다. O(n + m).
[Algorithm] C++ 백준 17955번 Max or Min

[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++ 백준 3654번 : L퍼즐

격자에서 빈 칸을 L자 타일로 겹치지 않게 모두 덮을 수 있는지 판정하는 문제입니다. 그래프 모델링과 최대 유량(디닉) 알고리즘을 활용하여, 각 칸을 노드로 변환하고 L자 타일의 배치 가능성을 간선으로 연결해 해를 구합니다. C++로 효율적으로 구현하는 방법과, 이분 그래프, 유량 네트워크의 개념, 좌표 매핑 및 간선 구성 등 다양한 알고리즘적 아이디어를 다룹니다.
[Algorithm] C++ 백준 3654번 : L퍼즐