My life story

1. 문제 링크 www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 2. 문제 개요 간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자. - 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 3. 문제 힌트 정점의 개수가 100,000개. 쿼리의 개수도 100,000개. 쿼리를 입력 받을 때, O(n^2)의 시간으로 처리했다가는 제 시간 안..

1. 문제 링크 www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 2. 문제 개요 반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다. 이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오. 3. 문제 힌트 처음에 문제를 읽었을 때 갔던 곳을 또 갈 수 있다는..

1. 문제 링크 www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 2. 문제 개요 동전을 움직일 건데, i) 동전이 있는 곳에 쓰여 있는 숫자 X를 본다. ii) 위, 아래, 왼쪽, 오른쪽 방향 중에 한 가지를 고른다 iii) 동전을 위에서 고른 방향으로 X만큼 움직인다, 이때, 중간에 있는 구멍은 무시한다. 3. 문제 힌트 정답률이 상당히 낮다. 나도 문제 풀 때 고려하는 거 다 고려했다고 생각했는데 틀려버린.. 고려해야 하는 것부터 적어본다면, 일단, 보기..

1. 문제 링크 www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2. 문제 개요 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 관계가 존재하는지 안 하는지 구하는 프로그램을 작성하시오. 오랜만에 DFS문제를 풀었는데 처음 생각을 잘못해서 10%쯤에서 계속 틀렸다.. 끙끙 앓다가 풀고 나니 허탈한 문제. 3. 문제 힌트 결국 문제의 의미는 4번 연속으로 연결되는, DFS를 할 때 깊이가 4인 것이 단 한 개라도 있으면 1을 출력하면 된다. 위의 가..