본문 바로가기

TRAVERSAL

[BOJ] 백준 2263번 트리의 순회 (Java)
Dot Algo∙ DS/PS 2021. 7. 25. [BOJ] 백준 2263번 트리의 순회 (Java) #2263 트리의 순회 난이도 : 골드 3 유형 : 트리 / 분할 정복 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net ▸ 문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. ▸ 입력 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. ▸ 출력 첫째 줄에 프리오더를 출력한다. 문제 풀이 preord..
[BOJ] 백준 1949번 우수 마을 (Java)
Dot Algo∙ DS/PS 2021. 5. 25. [BOJ] 백준 1949번 우수 마을 (Java) #1949 우수 마을 난이도 : 골드 1 유형 : 트리 순회/ DP 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net ▸ 문제 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있..
[BOJ] 백준 2213번 트리의 독립집합 (Java)
Dot Algo∙ DS/PS 2021. 5. 24. [BOJ] 백준 2213번 트리의 독립집합 (Java) #2213 트리의 독립집합 난이도 : 골드 1 유형 : 트리 순회/ DP 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net ▸ 문제 그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 에지가 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로..

티스토리툴바

티스토리툴바