Tags

11 pages

Divide and Conquer

[Algorithm] cpp 백준 10076번: 휴가 - 최적 풀이

IOI 2014 Holiday(휴가) 최적 풀이. 선형 도시에서 하루에 이동 또는 방문만 가능한 제약에서 방문 관광지 수를 최대화한다. 이동은 한 번의 방향 전환만 해도 충분하다는 관찰 아래 [l,r] 구간을 잡고 체류 가능일 g(l,r)을 계산한다. 분할정복+세그먼트 트리로 상위 k 합을 빠르게 질의하여 O(N log^2 N)로 해결한다. 경계·중복·음수 k 처리와 좌우 반전까지 구현 체크리스트 포함.
[Algorithm] cpp 백준 10076번: 휴가 - 최적 풀이

[Algorithm] cpp 백준 8987번: 수족관 3 - 카르테시안 트리

수평 바닥을 구간 높이 배열로 모델링한 뒤, 최소 높이 기준으로 구간을 분할하는 카르테시안 트리를 구성해 각 노드 직사각형 넓이를 계산합니다. 분할로 얻는 이득을 우선순위 큐에 넣어 상위 K개를 합하면 최대 배수량을 얻습니다. 구현은 O(N)~O(N log N)으로 안정적이며, 64-bit 정수 오버플로와 구간 경계 처리, 입력 형식 차이 등을 면밀히 점검합니다.
[Algorithm] cpp 백준 8987번: 수족관 3 - 카르테시안 트리

[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