전체 글 썸네일형 리스트형 BOJ 24231 해석 https://www.acmicpc.net/problem/24231 24231번: 해석 $($와 $)$로만 이루어진 문자열을 괄호 문자열이라고 한다. 괄호 문자열 중, 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 한다. 빈 문자열은 올바른 괄호 문자열이다. $A$가 올바른 괄 www.acmicpc.net 컨디션 난조로 3주만에 처음으로 문제를 풀어봤다. 어떠한 암호 문자열이 주어졌을 때, 이 암호 문자열을 분해하는 방법은 아래의 두 가지 방법이 있다 AB - A와 B모두 올바른 암호 문자열. 대응 가능한 괄호 문자열 -> (...)(...) xAy - A는 올바른 암호 문자열, x와 y는 서로 다른 암호 문자. 대응 가능한 괄호 문자열 ((..)) 주어진 문자열을 부분 문자열로 분해하여 각각 문.. 더보기 BOJ 11717 Wall Making Game (Game Theory) https://www.acmicpc.net/problem/11717 11717번: Wall Making Game The first line of the input consists of two integers H and W (1 ≤ H, W ≤ 20), where H and W are the height and the width of the board respectively. The following H lines represent the initial board. Each of the H lines consists of W characters. The j-t www.acmicpc.net 전형적인 impartial game으로 스프라그-그런디 정리(Sprague-Grundy Theorm)를 이용하는 것이 .. 더보기 BOJ 10531 Golf Bot (FFT) https://www.acmicpc.net/problem/10531 10531번: Golf Bot Do you like golf? I hate it. I hate golf so much that I decided to build the ultimate golf robot, a robot that will never miss a shot. I simply place it over the ball, choose the right direction and distance and, flawlessly, it will strike the ball across www.acmicpc.net 200000 이하의 숫자로 이루어진 집합이 주어진다. 이어서 어떤 수들이 주어졌을 때, 앞서 주어진 집합의 원소 하나 혹은 두 .. 더보기 BOJ 6171 땅따먹기 (볼록껍질 최적화) https://www.acmicpc.net/problem/6171 6171번: 땅따먹기 (1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다. www.acmicpc.net 볼록껍질 최적화가 일감 이었으나 쉽게 점화식을 유도하지는 못했다. 우선 두 개의 땅 a, b에 대해서 W_a >= W_b 이고 H_a >= H_b 이면, 땅 b는 땅 a와 한 묶음으로 사는게 무조건 이득이다(추가 비용이 발생하지 않는다). 전처리를 해서 b와 같은 땅을 모두 걸러낸 뒤, 너비에 대해서 오름차순으로 정렬을 하면 높이는 내림차순으로 정렬이 된다. 너비에 대해 정렬이된 세 개의 땅 a, b, c를 생각해보자. 이때 (a, c.. 더보기 BOJ 17429 국제 메시 기구 https://www.acmicpc.net/problem/17429 17429번: 국제 메시 기구 첫째 줄에 N, Q가 주어진다. (1 ≤ N ≤ 500,000, 1 ≤ Q ≤ 100,000) 다음 N-1줄 중 i번째 줄에는 Si, Ei가 주어지며, 이는 금고 Si와 금고 Ei가 연결되어 있다는 뜻이다. (1 ≤ Si, Ei ≤ N) 금고가 연결된 모 www.acmicpc.net 1감은 HLD를 이용한 풀이인데, 서브 트리 쿼리 처리를 어떻게 하는지에서 생각하느라 고생을 많이 했다. 우선 서브 트리 쿼리는 오일로 경로 테크닉을 이용해서 트리를 일자로 늘어뜨리면 해결이 된다. 트리를 순회(preorder traverse)하면서 노드의 발견 시각과 종료시각을 기록한다. 노드의 발견시각을 그 노드의 인덱스로 .. 더보기 이전 1 2 3 4 5 ··· 36 다음