이동식 저장소

왜냐고? 그것이 교수님이니까.. 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 2년 전에 못 푼 문제라 다시 도전해 봤는데, 그때의 내가 못 푼 이유가 있구나... 도저히 풀지 못할 것 같아 답을 봤다. 이 글은 타인의 풀이를 공부하여 정리한 것이다. 몇몇 물체간의 무게 관계가 주어졌을 때, 현재 가지고 있는 정보만으로 두 물체의 무게 차이를 구할 수 있는지, 구할 수 있다면 그 값은 몇인지 구하는 문제이다. 골드와 플레 실력을 나누는 쿼리 문제. 흠... 언뜻 보면 LCA라고 ..

주말 특집 플래티넘 풀이 시간! 1184번: 귀농 상근이와 선영이는 도심 속의 삶에 싫증을 느꼈고, 친구 현수가 있는 시골로 농사를 지으려 내려왔다. 현수의 땅은 크기가 N×N 인 정사각형이고, 땅은 단위 정사각형 1×1로 나누어져 있다. 각 단 www.acmicpc.net 합이 같고 한 점에서만 만나는 두 직사각형 구역의 쌍이 몇 개 있는지 구하는 문제이다. 두 직사각형이 한 점에서 만나는 경우는 빨간 기준점을 기준으로 좌상-우하 방향에서 만나는 경우와 좌하-우상 방향에서 만나는 경우 두 가지이다. 따라서 기준점을 먼저 잡은 후, 좌상-우하 두 방향에서 만들 수 있는 모든 직사각형의 쌍을 비교하고, 좌하-우상 방향으로도 동일하게 비교하면 된다. 참 쉽죠? 쉽지 않다 위의 풀이를 어떻게 구현할 것인가? ..

14711번: 타일 뒤집기 (Easy) 지구이는 신기한 게임판을 가지고 있다. 이 게임판에는 한 면은 검은색, 한 면은 흰색으로 칠해진 타일이 N행 N열으로 배치되어 있다. 각 타일은 제자리에서 뒤집을 수 있는데, 타일 하나를 뒤집 www.acmicpc.net 처음에 검은색이었던 타일을 모두 뒤집었을 때 모든 타일이 흰색이 되는 게임판을 만들어야 한다. 타일을 홀수 번 뒤집으면 색이 바뀌고, 짝수 번 뒤집으면 색이 바뀌지 않는다. 일단 첫 줄은 주어져 있으므로 나머지 줄을 완성해 보자. 칸의 색은 주변 4칸의 색에 의해 결정된다. 지구이의 동생이 검은색 타일만을 뒤집으므로, 주변에 검은색 타일이 홀수 개 존재한다면 이 칸의 색은 바뀐다. 반대로 검은색 타일이 짝수 개 존재한다면 이 칸의 색은 바뀌지 않는..

백준을 처음 풀었을 때부터 자주 보던 문제이다. 볼 때마다 음~ 어렵군 하고 넘겼던 기억이 있는데, 데일리 스터디에서 풀 문제로 선정되는 바람에...... 어차피 모르는 문제이므로 스스로 푸는 건 깔끔하게^^ 포기했고, 그래프 공부하는 겸 글을 작성해 본다. 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 최대 이분 매칭 (Maximum Bipartite Matching) 이분 그래프에서 서로 다른 집합에 속하는 정점을 연결하는 간선을 이분 매칭이라고 한다. 한번 매칭에 사용한 정점을 다시 사용하지 않으면서 최대한 많은 매칭..

22343번: 괄호의 값 비교 첫 번째 테스트 케이스: f[A] = f[((()))] = 4이고, f[B] = f[()(())] = 3이므로, f[A] > f[B]이다. 두 번째 테스트 케이스: f[A] = f[(((())))] = 8이고, f[B] = f[()()()()()] = 5이므로, f[A] > f[B] 이다. www.acmicpc.net 올바른 괄호 문자열 $A$, $B$가 주어졌을 때, $f[A]$와 $f[B]$를 비교하는 문제이다. 값을 비교하는 것이 목적이므로 값을 구하지 않아도 되지만, 다른 방법이 떠오르지 않아 그냥 구하기로 결정. 그런데 문제가 있다. 주어지는 문자열의 길이가 최대 300만이라 $f[A]$의 최댓값이 $2^{1500000}$이다. 로그를 적용해 보려 해도 $f[()]..