Tags

29 pages

Array

[Algorithm] C++ 백준 5920번: Cow Photography

BOJ 5920 Cow Photography 문제는 다섯 장의 사진에서 최대 한 번씩만 자리를 옮긴 소들의 줄 서기 결과를 보고, 원래 의도된 순서를 복원하는 순열 재구성 문제입니다. 각 쌍의 소에 대해 다섯 사진에서의 상대적 순서를 다수결로 비교하는 아이디어를 사용해, 안정적인 커스텀 정렬 비교 함수를 설계하고 C++로 O(N log N)에 유일한 답을 구하는 방법을 정리합니다.
[Algorithm] C++ 백준 5920번: Cow Photography

[Algorithm] C++ 백준 13546번: 수열과 쿼리 4 - Mo+제곱근분할

구간 [L,R]에서 같은 값의 두 위치 간 최대 거리(max |x−y|, A[x]=A[y])를 묻는 질의를 Mo 알고리즘으로 처리합니다. 값별 위치 데크와 거리 빈도(√ 분할)를 유지해 추가/제거 O(1)로 갱신하고, 블록 카운팅으로 최대 거리를 즉시 찾습니다. 경계 이동 순서·인덱스 변환·거리 갱신 누락 실수를 방지하는 체크리스트까지 정리했습니다.
[Algorithm] C++ 백준 13546번: 수열과 쿼리 4 - Mo+제곱근분할

[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++/Python 백준 1126번 : 같은 탑

백준 1126번 '같은 탑' 문제는 여러 블록을 이용해 두 탑의 높이를 동일하게 만들되 가장 높은 탑의 높이를 최대화하는 최적화 문제입니다. 동적 계획법(DP)을 활용하여 두 탑의 높이 차이와 누적 높이를 효율적으로 관리하며, 상태 전이와 초기화 방안, 구현 방법을 상세하게 다룹니다. 본 글은 C++/Python 예제 코드 및 핵심 아이디어를 포함하여 문제 해결에 필요한 핵심 로직과 최적화 전략을 설명합니다.
[Algorithm] C++/Python 백준 1126번 : 같은 탑