Codeforces Round 886 (Div. 4) 주요 문제별 최적화 알고리즘 해설
전반적으로 난이도가 낮았으나, 특정 문제에서는 접근 방식의 세부적 오류가 성능 저하를 유발할 수 있었다. 특히 E 문제와 같이 이분 탐색을 활용할 때는 범위의 정확한 설정이 중요했으며, F 문제에서는 초기 입력 해석의 부주의가 문제를 복잡하게 만들었다. 이하에서는 각 문제별로 효율적인 구현 방식을 검토하고 최적화 코드를 제시한다.
문제 D: 구간 연결성 최적 ...
9월 17일 14:08에 게시됨
Codeforces Round 903 (Div. 3) 풀이
이번 라운드의 A~G번 문제에 대한 핵심 아이디어와 구현 방법을 정리합니다.
A. Don't Try to Count
문자열 t가 s의 연속 부분문자열이 되도록 만드는 문제입니다. s를 반복하여 이어붙이면 길이가 2배로 늘어나는 특성을 활용합니다. n·m ≤ 25 조건 덕분에 최대 5번만 반복하면 충분합니다.
#include <bits/stdc++.h>
using namespace std;
bool isSubstr(const s ...
7월 31일 23:32에 게시됨
Codeforces Global Round 27 문제 분석 및 풀이
A번: 빨간 점 제거 후 남은 영역 계산
격자판에서 특정 위치 (r, c)의 빨간 점을 제거했을 때, 나머지 칸들을 세 가지 구역으로 나누어 계산한다. 오른쪽에 있는 열들은 각 행마다 m - c칸만큼 이동하며 영향을 받고, 아래쪽 행 전체는 m * (n - r)만큼 더해진다. 마지막으로 대각선 아래 왼쪽 부분은 (m - 1) * (n - r)로 계산할 수 있다. 최종 답은 이 세 값을 합한 것이 ...
7월 31일 20:29에 게시됨
Codeforces Round 960 (Div. 2) 효율적인 문제 풀이 전략
A. Submission Bait (게임 이론)
앨리스와 밥이 $n$개의 원소를 가진 배열 $a$를 사용하여 게임을 진행합니다. 초기 mx 값은 0이며, 각 플레이어는 자신의 차례에 $a_i \ge mx$인 인덱스 $i$를 선택하여 mx를 $a_i$로 갱신하고 $a_i$를 0으로 만듭니다. 더 이상 움직일 수 없는 플레이어가 패배할 때, 앨리스의 필승 전략 존재 여부를 판별해야 합니다.
이 문제의 핵심은 ...
7월 30일 12:49에 게시됨
Codeforces Round 920 (Div. 3) 효율적인 문제 해결 접근법
Problem A: Square
이 문제는 2차원 평면 위에 놓인 정사각형의 네 꼭짓점 좌표가 주어졌을 때, 해당 정사각형의 넓이를 구하는 문제입니다. 정사각형의 변은 항상 x축 또는 y축에 평행하다는 조건이 있습니다.
네 점의 좌표 중에서 x좌표가 같은 두 점을 찾으면, 그 두 점의 y좌표 차이의 절댓값이 바로 한 변의 길이(a)가 됩니다. 따라서 넓이는 a의 제곱으로 계산할 수 ...
7월 27일 18:21에 게시됨
Codeforces Round #727 (Div. 2) A-D 문제 풀이
A. Contest Start (수학)
이 문제는 패턴을 분석하는 문제입니다. 참가자들의 시작 시간이 일정한 간격으로 배치될 때, 각 참가자가 기다려야 하는 평균 시간을 구해야 합니다.
먼저, 한 참가자가 끝날 때까지 기다리는 다른 참가자의 수를 생각해봅시다.
만약 한 참가자의 경기 시간이 \(t\)이고, 다음 참가자와의 시작 시간 차이가 \(x\)라면, 한 참가자가 경기하는 동 ...
7월 26일 14:19에 게시됨
Codeforces Round 891 Div.3 문제 복기 및 풀이 해설
개요
첫 CF Div.3 대회 참가 후, T2의 문제를 오독하고 T3에서 무리한 구조 설계로 실패한 경험을 바탕으로 복기하며 각 문제를 해석하고 해결 방안을 정리한다.
A. 배열 분할과 합의奇偶성
문제 요약: 주어진 배열을 두 부분으로 나누어 각 부분의 합의 홀짝성이 동일하도록 만들 수 있는지 판단한다.
해석 및 분석: 홀수(odd)와 짝수(even)의 합 연산 규칙은 다음과 같 ...
7월 17일 21:47에 게시됨
Codeforces 2133 문제 분석 및 풀이
C The Nether: DAG에서 최장 경로 탐색
이 문제는 그래프의 구조를 쿼리하는 방식으로 해결하는 인터랙티브 문제입니다. 주어진 방향성 비순환 그래프(DAG)에서 가능한 최대 길이의 경로를 찾아야 하며, 쿼리 제한은 2n번입니다.
핵심 전략은 각 정점에서 시작하는 최장 경로 길이를 미리 계산한 후, 그 중 가장 큰 값을 가진 정점을 시작점으로 삼고, 이후 점차 이어지는 ...
7월 10일 18:44에 게시됨
Codeforces Round 991 (Div. 3) F - 구간 최대公约수와 차분 배열
문제 접근
이 문제는 구간 내에서의 최대公约수(GCD) 값을 구하는 문제이다. 핵심 아이디어는 차분(difference) 배열을 활용하는 것이다. 원래 배열에서 인접한 요소들의 차이를 구하면, 해당 구간의 GCD는 차분 배열의 특정 구간 GCD와 동일해진다.
따라서 우리는 구간 GCD를 효율적으로 구할 수 있는 자료구조를 사용하면 된다. 두 가지 대표적인 방법을 소개한다.
방 ...
7월 10일 06:27에 게시됨
다이나믹 프로그래밍 문제 풀이 모음
목차
백준 4933 - 마스터 (선형 DP)
백준 5858 - 황금 검 (선형 DP)
백준 1280 - 닉의 임무 (선형 DP)
USACO 2016 오픈 - 2048 (구간 DP)
백준 2585 - 삼색 이진 트리 (트리 DP)
백준 1441 - 추 저울질 (조합 탐색 + 배낭)
백준 1896 - 서로 공격하지 않음 (비트마스크 DP)
Codeforces 1488E - 회문 쌍 (LIS 응용)
Codeforces 1486D - 최대 중앙값 (이분 탐색)
Codeforces ...
7월 9일 04:00에 게시됨