Codeforces Round 1029 Div.3 A-D번 문제 해설
A. False Alarm
문제의 지시에 따라 직접 구현하면 됩니다. 1이 등장하는 위치들을 기록하고, 인접한 1들 사이의 거리를 누적하여 총 소요 시간을 계산합니다.
정답 코드:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
while (tc--) {
...
6월 18일 01:45에 게시됨
USACO 2022년 11월 대회 문제 풀이: 외톨이 사진과 단어 맞추기
문제 1: 외톨이 사진(Lonely Photo)
농장주 존이 N마리의 소를 새로 샀다. 각 소는 게른지(Guernsey) 또는 홀스틴(Holstein) 품종이다. 소들이 한 줄로 서 있을 때, 길이가 3 이상인 모든 연속 구간에 대해 사진을 찍는다. 단, 구간 내에 특정 품종이 정확히 한 마리만 존재하는 "외톨이 사진"은 폐기처분한다. 폐기되는 사진의 총 개수를 구하라.
입력
첫 줄: N (소의 ...
6월 16일 01:00에 게시됨
백트래킹, 그리디, 분할정복, 동적계획법 알고리즘 비교
백트래킹 알고리즘
백트래킹은 해결 가능한 모든 경로를 탐색하는 알고리즘으로, 재귀 호출을 통해 결정 트리를 탐색하며 실패 시 이전 상태로 돌아가는 방식을 사용합니다.
def backtrack(current_path, choices):
if is_solution(current_path):
add_to_result(current_path)
return
for choice in choices:
if not is_valid(ch ...
6월 15일 16:23에 게시됨
중산 집중 훈련 기록 (7.28–8.11)
7월 29일
주로 모의고사 중심으로 진행되었으며, 일부 문제에 대한 분석과 후기 포함.
T1
간단한 시뮬레이션 문제. CSP-S2023 T3보다도 쉬웠다. 디버그 문구를 지우지 않아서 실수했지만, 다행히 오답은 아니었다. 복잡도가 높을 수 있다는 점을 인지하고, 더 효율적인 접근 방식을 고려해야 한다. 결국 코드는 통과했으나, 조건이 애매하면 예외 처리가 필요하다.
T2
초기 ...
6월 11일 20:47에 게시됨
LeetCode 2270: 누적합을 활용한 배열 분할 조건 탐색
문제 이해LeetCode 2270번 Split Array Largest Sum과 유사한 조건으로, 배열을 두 부분으로 나누었을 때 왼쪽 구간의 합이 오른쪽 구간의 합 이상이 되는 분할 지점의 개수를 구하는 문제입니다.길이가 n인 배열 nums에서 인덱스 i (0 ≤ i < n-1)를 기준으로 분할할 때, 다음 조건을 만족하면 유효한 분할입니다:sum(nums[0..i]) ≥ sum(nums[i+1..n-1])핵심 관찰전체 ...
6월 6일 21:21에 게시됨
9월 6일 알고리즘 대회 풀이
$$100 + 90 + 65 + 0 = 255$$점, 학내 $$rk7$$. 링크
T1
분류: 가볍게 풀 수 있는 문제 (노란색 난이도)
문제의 핵심은 반전 연산의 특성이다. 두 위치가 서로 다르다면, 그 중 하나만 바꾸는 것이 아니라, 인접한 두 위치가 서로 순서가 잘못되어 있을 때에만 동시에 교환하는 것이 최적임을 알 수 있다. 따라서 단순한 그리디 시뮬레이션으로 해결 가능하며, 시간 복잡도 ...
5월 29일 13:16에 게시됨
소수점 버림 조건을 만족하는 쌍 계산 및 비트 연산자 배열 최적화
문제 A: 조건부 쌍 카운팅
분수 i/j의 소수부가 0.5 미만이 되도록 하는 (i, j) 쌍의 개수를 구하는 문제입니다. 수학적으로 변형하면:
i/j - ⌊i/j⌋ < 0.5
양변에 j를 곱하면 i - ⌊i/j⌋·j < 0.5j가 됩니다. 여기서 왼쪽 항은 나머지 연산 i % j와 동일하므로, 최종 조건은 i % j < 0.5j로 단순화됩니다.
구간 패턴 분석
고정된 j에 대해 i가 0부터 n까지 변 ...
5월 27일 21:09에 게시됨
코드포스 대회 문제 풀이: B, C번 풀이 모음
최근 진행된 Codeforces 대회들의 주요 문제 풀이를 모아서 정리했습니다. 각 문제는 배열 처리, 구간 합, 그리디 알고리즘 등의 기법을 활용하여 효율적으로 해결할 수 있습니다.
Educational Codeforces Round 132 (Div. 2) – B번
수열이 주어질 때 특정 구간에서 인접 원소 간 차이의 합을 구하는 문제입니다. 오른쪽으로 이동할 때 증가 폭과 감소 폭을 각각 별도로 ...
5월 22일 09:50에 게시됨