Bibidi

4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 1. Preorder는 루트, 왼쪽, 오른쪽 순으로 방문하므로 제일 먼저 출력하는 정점은 항상 탐색하려는 트리의 루트이다. 2. Inorder는 왼쪽, 루트, 오른쪽 순으로 방문하므로 루트를 기준으로 왼쪽에 있는 정점들은 루트의 왼쪽 서브 트리, 오른쪽에 있는 정점들은 루트의 오른쪽 서브 트리를 구성하는 정점들이다. 3. 위 성질을 이용하여, Preorder의 탐색 순서에 맞추어 Inorder 내의 정점들을 잘 잘라나가면 원래의 트리를 구할 수 있다...

2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 1. 각 노드의 열은 왼쪽에 있는 노드들의 개수 + 1이다. 왼쪽 서브 트리에 속하는 노드의 개수와 왼쪽에 있지만 서브 트리에 속하지 않는 노드를 잘 파악해야 한다. 왼쪽 서브트리의 개수는 재귀를 이용하여 구하고 그 외의 노드는 따로 매개변수를 이용하여 전달하여야 한다. 2. 각 깊이의 가장 왼쪽 열과 가장 오른쪽 열을 파악하면 각 깊이의 최대 너비를 알 수 있다. 노드를 방문할 때마다 업데이트 해주고 마지막에 최대 너비와 그 깊이를 구하면 된..

16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 경로가 겹치는 양들 다 모아서 한 번에 지나간다고 생각하고 구현하면 된다. 늑대가 양을 여러 번 잡아먹는 구현만 피하면 간단하다. - Source code link github.com/Bibidi/Algorithms/blob/master/boj/boj%2016437.cpp

4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net Undirected graph에서 cycle만 없으면 트리이고 cycle을 찾는 방법은 간단하다. 현재 노드에서 다음 노드를 방문하려고 검사할 때, 다음 노드가 이미 방문한 노드인데 바로 이전에 방문했던 노드가 아니면 cycle이다. - Source code link github.com/Bibidi/Algorithms/blob/master/boj/boj%204803.cpp

11997번: Load Balancing (Silver) Farmer John's \(N\) cows are each standing at distinct locations \((x_1, y_1) \ldots (x_N, y_N)\) on his two-dimensional farm (\(1 \leq N \leq 1000\), and the \(x_i\)'s and \(y_i\)'s are positive odd integers of size at most \(1,000,000\)). FJ wants to par www.acmicpc.net 1. N은 기껏해야 1000이지만, 좌표 범위가 1e6이므로 좌표 압축을 해서 위치를 다시 그리는 과정이 필요함. 중복을 지우는 데에 set을 이용했음. 2. 이제 네..

1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 꽤 재밌었던 문제. 왔던 방향으로 다시 되돌아가야 되는 경우가 있어서 처음엔 어떻게 구현해야할지 몰라서 계속 헤맸다. 열쇠를 새로 얻으면 벽에 부딪히고 다시 되돌아갈 수 있게 해야 하나 등등의 오만 생각이 다 들었으나, 현재 내가 어떤 상태에 놓여있는지 정의하면 문제가 간단해지는 걸 깨달음. int 하나를 내가 획득한 열쇠로 정의하고 내가 지금 이러한 열쇠를 얻은 상태에서 내가 가려는 지점을 방문한 적이 있는지 체크하면 중복을 방지..

1327번: 소트 게임 첫째 줄에 순열의 크기 N과 K가 주어진다. N은 2보다 크거나 같고, 8보다 작거나 같다. 둘째 줄에 순열에 들어가는 수가 주어진다. www.acmicpc.net bit 최적화 연습용 문제 1. int형 숫자를 3bit씩 나눠서 각 3비트가 하나의 숫자를 나타내도록 함. 100은 1, 010은 2, 001은 4를 나타냄. 원래 표기법과 반대지만 구현은 이쪽이 더 편함. 2. BFS를 이용해서 풀었고 중복 체크는 set을 이용했음. 구현 #include using namespace std; typedef long long ll; const int INF = 2e9; int n, k; void setDigit(int &bit, int k, int num) { for (int i = ..

1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 1. 간단한 문제지만 c++ cout 정밀도 때문에 기록함. cout