경쟁 프로그래밍 해설: 문자열 처리와 조합적 동적 계획법

문자열 패턴 변환 최소화 주어진 문자열에서 특정 패턴이 나타나지 않도록 비트 반전 작업을 수행하는 최소 횟수를 구하는 문제입니다. 타겟 패턴의 길이가 1, 2, 3 으로 제한되어 있어, 길이별로 경우를 나누어 접근해야 합니다. 패턴 길이가 1 일 때는 문자열에 해당 숫자가 아예 없어야 하므로 단순 반복 검사로 해결 가능합니다. 길이가 2 인 경우는 대칭성과 보수 연 ...

10월 10일 06:40에 게시됨

조합 수학 문제 풀이 전략: 구간 합과 DP 최적화

복잡한 조합 계산 문제는 단순한 공식 적용보다는 상태 정의와 전이 과정의 논리적 정합성을 따져보는 것이 중요합니다. 아래에서는 기하학적 기여도 분할, 비트 연산을 활용한 부분집합 DP, 그리고 순서 있는/없는 색칠 문제 등 다양한 유형의 조합 카운팅 문제를 분석합니다. 1. 직사각형 내 점 선택 및 좌표별 기여도 분리 $n \times m$ 크기의 격자에서 $k$개의 점을 ...

9월 23일 14:02에 게시됨

C++로 구현하는 정보 올림피아드 문제: 장비 합성 시스템

문제 설명 특정 게임에서는 다양한 장비를 수집하고 강화할 수 있는 시스템이 존재한다. 각 장비는 여러 개의 슬롯을 가지며, 각 슬롯에는 특정 가치를 가진 인쇄물이 무한히 존재한다. 게임 내 특정 캐릭터(예: 카구야마 하루카)가 기계 팔을 사용해 아래 방향으로만 움직이며 인쇄물을 추출한다. 이때 기계 팔은 오른쪽으로 이동하거나 제자리에 머무를 수 있으며, 시작 ...

8월 2일 18:30에 게시됨

NOIP2018 Day2T2 填数游戏

이 문제는 n×m 격자에 0과 1을 채워넣는 방식의 수를 세는 조합 문제입니다. 핵심 조건은 오른쪽 우선 경로의 01 문자열이 아래쪽 우선 경로의 01 문자열보다 사전순으로 작거나 같아야 한다는 것입니다. 작은 케이스 분석과 패턴 발견 먼저 n ≤ 3인 경우를 완전탐색으로 해결할 수 있습니다. DFS를 통해 모든 가능한 배치를 검증하면 다음과 같은 결과를 얻습니다: 2 : ...

7월 23일 22:03에 게시됨

문자열 해시와 선분 트리, 트리 DP, 비트셋을 활용한 정사각형 탐색 문제 풀이

문제 1: 동적 문자열 집합에서 고유 문자열 수 계산 여러 개의 동일 길이 문자열이 주어지고, 각 쿼리마다 특정 문자열의 부분 구간을 같은 문자로 덮어쓴 후, 전체 집합 내 서로 다른 문자열의 개수를 출력해야 한다. 해결 핵심은 다음과 같다: 각 문자열의 해시 값을 효율적으로 갱신하기 위해 게으른 전파(lazy propagation)가 가능한 선분 트리를 사용한다. 해시 ...

7월 20일 20:48에 게시됨

정수론과 기하학적 최적화를 활용한 알고리즘 문제 해결

약수 관계를 가진 정수 삼원조의 개수 구하기 양의 정수 \(n\)이 주어졌을 때, 다음의 조건을 모두 만족하는 정수 삼원조 \((a, b, c)\)의 개수를 구하는 문제입니다. \(a + b + c = n\) \(1 \le a < b < c \le n\) \(a\)는 \(b\)의 약수이고, \(b\)는 \(c\)의 약수이다. 이 문제의 핵심은 약수 관계를 매개변수로 치환하여 식을 단순화하는 것입니다. ...

6월 27일 04:21에 게시됨

Java 알고리즘 풀이: 텐센트 2018 상반기 채용 기출 문제

문제 1: 교차 부호 수열의 합 길이 n의 연속된 정수 수열 1, 2, 3, ... n에 대해, 매 m개마다 부호를 교차시키는 수열을 정의합니다. 초기 부호는 음수(-)이며, 부호는 -, -, ..., +, +, -, -, ... 순서로 반복됩니다. 이때 처음 n개 항의 총합을 구하는 문제입니다. 입력 조건: 두 정수 n, m (2 ≤ n ≤ 10⁹, 1 ≤ m), n은 2m으로 나누어 떨어짐 출력: 처음 n개 항의 합 ...

6월 6일 22:56에 게시됨

h-index 계산 및 구간 합 나머지 연산 등 주요 알고리즘 유형 정리

1. 최적의 h-index 산출 (이분 탐색) h-index는 연구자가 발표한 논문 중 인용 횟수가 h회 이상인 논문이 h편 이상일 때, h의 최댓값을 의미합니다. 추가적으로 L회의 인용 횟수를 논문들에 배분하여(논문당 최대 1회) h-index를 높일 수 있는 경우, 이분 탐색을 통해 최적의 값을 찾을 수 있습니다. #include <iostream> #include <vector> #include <alg ...

5월 30일 12:16에 게시됨

2025 NOI 문제 풀이 기록 (2)

By DaiRuichen007 라운드 #65 - 20250326 A. [AT-CF17-F] 숫자 분배 문제 링크 문제 요약 \(\text{정수 } n \in [1000, 2000], k \text{를 선택하여},\) 크기가 \(k\)인 \([1,n]\)의 부분집합을 \(n\)개 만들되, 임의의 두 집합 간 교집합 크기는 \(1\)이 되고, 각 원소는 정확히 \(k\)번 등장하도록 한다. 해법 분석 모든 집합 쌍이 공통 원소를 가지도록 하기 위해, ...

5월 24일 11:47에 게시됨