이동식 저장소

1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다. 이 나라의 주민들에게 성취감을 높여 주 www.acmicpc.net 그래프에서 독립 집합은 다음과 같이 정의된다. 그래프의 모든 정점 V의 부분집합 S에 대하여, 임의의 S의 두 정점 사이를 연결하는 간선이 없을 때 S를 독립 집합이라고 한다. 독립 집합의 크기는 정점..

2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다. www.acmicpc.net 트리를 격자판에 그리려 한다. 격자판의 한 칸에는 노드 하나가 들어가며, 주어진 조건에 따라 그려야 한다. 가장 결정적인 조건은 3번 조건이다. 3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다. ..

글이 늦은 이유는 개강을 했기 때문.. 이라고 핑계를 대 본다. Dashboard - Codeforces Round #628 (Div. 2) - Codeforces codeforces.com 지난 div. 2에서 1문제밖에 풀지 못했던 아픔이 있기 때문에 이번에는 2문제를 확실하게 푸는 것으로 목표를 정했다. 3문제를 풀기에는 내 수면 패턴이 허락하지 않을 듯 하여.. 여느 때와 다름없이 A번을 읽는다. x가 주어질 때, GCD(a, b) + LCM(a, b) = x를 만족시키는 (a, b) 쌍을 구하시오. 쌍이 여러 개일 경우 아무거나 출력한다. 단, GCD(a, b)는 a와 b의 최대공약수이며 LCM(a, b)는 a와 b의 최소공배수이다. 문제를 보고 5분동안 브루트 포스에 대해 생각해 봤다. x가 ..

Dashboard - Codeforces Round #627 (Div. 3) - Codeforces codeforces.com 라운드 시작 시간이 밤 10시 5분으로 바뀌었다. 다른 온라인 대회와 시간이 겹쳐서 그랬다는데, 나에게는 매우 반가운 소식. 예전에 디비전 3을 연습했을 땐 3개 정도 풀었으니까, 이번에는 최소 3개+a로 목표를 잡았다. A번을 보자. 테트리스 판이 주어졌을 때, 2*1짜리 블럭만을 이용하여 게임을 클리어할 수 있는지 판별하는 문제이다. 이때 블럭을 회전시킬 수 없다. 간단하다. 모든 열의 높이가 같아져야 하는 것 아닌가? 그러려면 모든 열의 높이가 홀수 또는 짝수 중 하나여야만 한다. 각 열의 높이를 2로 나눠 주기만 하면 문제 해결. B번은 팰린드롬 문제이다. 수열 a의 부분..

예전부터 이런 류의 대회 시스템에 참가하고 싶은 마음은 있었지만, 내 실력으로 과연 의미 있는 결과를 얻을 수 있을까? 라는 의심이 있었다. 그래도 어쨌든 해 보는 게 낫지 않겠나 싶어서 2월달부터 대회에 참가하고 있다. 그런데 평일 대회는 전부 밤 11시 35분 시작이다.. 늦어도 12시 반에 자는 내가 참가하기엔 너무 늦다. ㅠㅠ 그렇긴 하지만 마냥 미루기만 할 수도 없는 까닭에.. 다른 대회보다 상대적으로 쉬운 Educational Round에 참가해 보았다. Dashboard - Educational Codeforces Round 83 (Rated for Div. 2) - Codeforces codeforces.com A번 문제를 보았다. 볼록 정 N각형 내부에서 중심이 동일한 정 M각형을 만들 ..