yunny.world

https://www.acmicpc.net/problem/18240 18240번: 이진 탐색 트리 복원하기 가능한 수열이 있다면 첫째 줄에 수열 A1, A2, ..., AN의 값을 공백으로 구분하여 출력한다. 가능한 수열이 여러 개라면 아무거나 출력해도 좋다. 가능한 수열이 없다면 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 이진 탐색 트리의 모양이 정해지면, (중위순회의 방문 순서) = (그 노드의 값)으로 해당 노드의 값을 찾을 수 있다. 다만, 이진 탐색 트리를 만들 수 없는 경우가 생기는데, 바로 앞에 깊이 i인 경우가 없는데 깊이 i+1인 경우가 나오는 경우이다. 이 경우를 자세히 살펴보면 아래와 같다. dep[i - 1] < dep[i] / 2 + 1 인 경우에는 깊이 i의 ..

https://www.acmicpc.net/problem/11581 11581번: 구호물자 서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했다. 강력한 폭풍의 영향으로 모든 사람은 대피소로 대피하였으며, 많은 도로가 유실되었다. 그나마 남아있는 도로도 모든 표지판과 가로등이 www.acmicpc.net 풀이 1번에서 DFS를 시작해서 사이클이 있는지 판단하면 된다. 이때, 정점을 3가지 상태로 표현해서 구현을 해야 한다. vi[i]의 값이 0일때, 아직 정점을 방문하지 않았다. 1일때, 정점을 방문 중이다. 2일때, 정점을 방문 완료했다. 정점을 방문 완료한 이후에는, 더이상 그 정점을 방문할 필요가 없다. 정점을 방문 중에, 그 정점이 호출되면 사이클이 존재한다. 코드 ll n; vector g[1..

https://codeforces.com/contest/1702 Dashboard - Codeforces Round #805 (Div. 3) - Codeforces codeforces.com A. Round Down the Price (00:04) 정수 m이 입력되면, m보다 작거나 같은 최대 \( 10^k \)꼴의 수와의 차를 출력해야한다. 나는 m를 문자열로 입력받아서, m-(1에 10를 m.length()-1번 곱한 수) 를 출력해 풀었다. B. Polycarp Writes a String from Memory (00:18) 그냥 구현 문제이다. 서로 다른 3개의 문자만 있는 부분 문자열의 개수를 세면 된다. 나는 서로 다른 3개를 저장하는 vector를 관리해서 풀었다. vector의 erase,..