본문 바로가기

Dot Algo∙ DS

[BOJ] 백준 12767번 Ceiling Function (Java)
Dot Algo∙ DS/PS 2021. 12. 16. [BOJ] 백준 12767번 Ceiling Function (Java) #12767 Ceiling Function 난이도 : 골드 1 유형 : 트리 / BST 12767번: Ceiling Function Advanced Ceiling Manufacturers (ACM) is analyzing the properties of its new series of Incredibly Collapse-Proof Ceilings (ICPCs). An ICPC consists of n layers of material, each with a different value of collapse resistance (measured as a positive integer). www.acmicpc.net ▸ 문제 Advanced Ceiling Manufacturers (ACM) is analyz..
[BOJ] 백준 4179번 불! (Java)
Dot Algo∙ DS/PS 2021. 12. 15. [BOJ] 백준 4179번 불! (Java) #4179 불! 난이도 : 골드 4 유형 : 그래프 탐색 / BFS 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net ▸ 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 ..
[BOJ] 백준 13244번 Tree (Java)
Dot Algo∙ DS/PS 2021. 12. 14. [BOJ] 백준 13244번 Tree (Java) #13244 Tree 난이도 : 골드 4 유형 : 그래프 / 트리 / Union-Find 13244번: Tree For each graph, a single line with “tree” if the graph represents a tree or “graph“ otherwise. www.acmicpc.net ▸ 문제 One of the most important data structures in computer science is the tree. You already dealt with binary trees in the qualification round. This problem is about general trees. Trees are the subset of graphs that have th..
[BOJ] 백준 6597번 트리 복구 (Java)
Dot Algo∙ DS/PS 2021. 12. 13. [BOJ] 백준 6597번 트리 복구 (Java) #6597 트리 복구 난이도 : 골드 3 유형 : 트리 순회 6597번: 트리 복구 창영이는 바이너리 트리를 매우 좋아한다. 그가 가장 좋아하는 게임은 바이너리 트리를 만들고, 노드에 알파벳 대문자를 하나씩 쓰는 것이다. 같은 알파벳을 여러 노드에 쓰지 않는다. 아래는 www.acmicpc.net ▸ 문제 창영이는 바이너리 트리를 매우 좋아한다. 그가 가장 좋아하는 게임은 바이너리 트리를 만들고, 노드에 알파벳 대문자를 하나씩 쓰는 것이다. 같은 알파벳을 여러 노드에 쓰지 않는다. 아래는 창영이가 만든 한 바이너리 트리이다. D / \ / \ B E / \ \ / \ \ A C G / / F 창영이는 후손들에게 물려주기 위해서, 만든 트리를 항상 종이에 적어놓는다. 이때, 트리를 프리오더 순회한 결과와 ..
[BOJ] 백준 9489번 사촌 (Java)
Dot Algo∙ DS/PS 2021. 12. 12. [BOJ] 백준 9489번 사촌 (Java) #9489 사촌 난이도 : 골드 4 유형 : 트리 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net ▸ 문제 증가하는 정수 수열을 이용해서 트리를 만드는 방법은 다음과 같다. 첫 번째 정수는 트리의 루트 노드이다. 다음에 등장하는 연속된 수의 집합은 루트의 자식을 나타낸다. 이 집합에 포함되는 수의 첫 번째 수는 항상 루트 노드+1보다 크다. 그 다음부터는 모든 연속된 수의 집합은 아직 자식이 없는 노드의 자식이 된다. 그러한 노드가 여러 가지 인 경우에는 가장 작은 수를 가지는 노드의 ..
[BOJ] 백준 2233번 사과나무 (Java)
Dot Algo∙ DS/PS 2021. 12. 11. [BOJ] 백준 2233번 사과나무 (Java) #2233 사과나무 난이도 : 골드 1 유형 : 트리 / LCA 2233번: 사과나무 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 2,000)이 주어진다. 둘째 줄에는 벌레가 만드는 2×N자리의 이진수가 주어진다. 셋째 줄에는 썩은 사과의 위치를 나타내는 두 정수 X, Y가 주어진다. 이는 2×N자리 www.acmicpc.net ▸ 문제 사과나무는 나무(tree)의 일종으로, 각각의 정점에 정확히 한 개의 사과가 있고, 모든 내부 정점(자식이 있는 정점)이 최소 두 개의 자식을 갖는 나무이다. 예를 들면 아래의 그림은 사과나무의 예이다. 나무같이 보이기 위해서 그림은 루트를 아래에 그린다. 이러한 사과나무에 서식하는 벌레를 생각해 보자. 이 벌레는 이 사과나무의 루트에서 DFS 순서로 탐색을 하게 된다. 자..
[BOJ] 백준 12784번 인하니카 공화국 (Java)
Dot Algo∙ DS/PS 2021. 12. 10. [BOJ] 백준 12784번 인하니카 공화국 (Java) #12784번 인하니카 공화국 난이도 : 골드 3 유형 : 트리 / DFS 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net ▸ 문제 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들어 모든 섬 간의 왕래가 가능하도록 만들었다. 1번섬에서 살고 있는 진은 어느 날 위험한 소문을 듣게 되었다. 1번섬을 제외한 다리가 하나밖에 없는 어느 섬에서 유명한 연쇄 살인마 괴도‘루..
[BOJ] 백준 11780번 플로이드 2 (Java)
Dot Algo∙ DS/PS 2021. 12. 9. [BOJ] 백준 11780번 플로이드 2 (Java) #11780 플로이드 2 난이도 : 골드 2 유형 : 그래프 탐색 / 플로이드 와샬 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ▸ 문제 n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. ▸ 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는..

티스토리툴바

티스토리툴바