트리

문제 링크https://www.acmicpc.net/problem/26260 문제김소마는 최근에 포화 이진 트리에 대해 배웠다. 포화 이진 트리란, 이진 트리에서 리프 노드를 제외한 모든 노드가 두 자식 노드를 가지며, 모든 리프 노드가 채워진 것을 말한다. 아래의 그림을 통해 쉽게 이해하자.  김소마는 예쁜 포화 이진 검색 트리를 그려 만족했지만, 밥 먹다 흘린 소스가 리프 노드 한 개를 가려버렸다. 여기서 이진 검색 트리란, 모든 왼쪽 자식이 자신보다 작고, 모든 오른쪽 자식이 자신보다 큰 이진 트리를 이야기한다.  그림을 버리려던 찰나, 김소마는 갑자기 포화 이진 검색 트리를 유지하며, 임의의 수를 넣을 때, 트리 구조가 어떻게 바뀔지 궁금해졌다. 멍청한 김소마를 위해 당신이 도와주자. 입력첫 번째..

문제 링크https://www.acmicpc.net/problem/15900 문제평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다.'나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다.이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임말이 하나..

문제 링크https://www.acmicpc.net/problem/20364 문제이진 트리 모양의 땅으로 이루어진 꽉꽉마을에는 오리들이 살고 있다. 땅 번호는 다음과 같이 매겨진다.루트 땅의 번호는 1이다.어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 × K, 오른쪽 자식 땅의 번호는 2 × K + 1이다.어느날 오리들끼리 부동산 다툼이 일어나서 꽉꽉마을 촌장 경완이가 해결책을 가져왔고, 그 내용은 다음과 같다.오리들을 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 위치해 있다.오리들이 서있는 순서대로 원하는 땅을 가지도록 한다. 만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을 지나가지 못해 그 오리는 땅을 가지지 못한..

문제 링크 https://www.acmicpc.net/problem/23835 23835번: 어떤 우유의 배달목록 (Easy) 이 문제는 "어떤 우유의 배달목록 (Hard)" 문제와 $N$, $Q$의 제한을 제외하고 같은 문제이다. SASA의 기숙사에는 $N$ 개의 방과 사감의 감시를 피하기 위해 만든 $N-1$개의 비밀 통로가 존재한다. 각 방 www.acmicpc.net 문제 이 문제는 "어떤 우유의 배달목록 (Hard)" 문제와 N, Q의 제한을 제외하고 같은 문제이다. SASA의 기숙사에는 N개의 방과 사감의 감시를 피하기 위해 만든 N - 1개의 비밀 통로가 존재한다. 각 방은 1번부터 N번까지의 번호가 붙어있다. 비밀 통로는 서로 다른 두 방을 양방향으로 연결하며, 임의의 두 방 사이를 비밀 ..

문제 링크 https://www.acmicpc.net/problem/28270 28270번: Marked-Numbered 코치 희승이는 FXC 나라 육상 국가대표 선발 보고서를 작성하였다. 희승이는 보고서를 작성할 때 목차를 육상협회에서 사용하는 글머리 기호 형태로 작성하였다. 희승이가 FXC 나라 문화체육관광 www.acmicpc.net 문제 코치 희승이는 FXC 나라 육상 국가대표 선발 보고서를 작성하였다. 희승이는 보고서를 작성할 때 목차를 육상협회에서 사용하는 글머리 기호 형태로 작성하였다. 희승이가 FXC 나라 문화체육관광부로 공문을 보내려고 봤더니, 문화체육관광부에서는 공문을 작성할 때 글머리 번호 형태로 작성한다. 따라서 희승이는 보고서를 글머리 번호 형태로 바꾼 사본을 만들어서 문화체육관광..