본문 바로가기
반응형

트리

 (3)
[백준] 무한이진트리(python) 백준, 무한이진트리 2078번: 무한이진트리 첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다. www.acmicpc.net TL;DR 트리(Tree) 수학(Mathematics) 문제 요약 1. 규칙에 의해 생성되는 무한 이진 트리에서 입력으로 받은 지점에 도착하기 까지 왼쪽 이동 횟수와 오른쪽 이동 횟수를 각각 구하는 프로그램을 작성하는 문제이다. 2. 규칙은 다음과 같다. 1. 루트에는 (1, 1)이 할당된다. 2. 어떤 노드 (a, b)가 할당되었을 때, 해당 노드의 왼쪽 자식은 (a + b, b)가 되고, 오른쪽 자식은 (a, a + b)가 할당된다. 3. 잘못된 입력은 주어지지 않는다고 가정한다. - 이진 트리에서 ..
[리트코드] Balanced Binary Tree(python) 리트코드, Balanced Binary Tree_균형 이진 트리 TL;DR 트리(Tree) 깊이 우선 탐색(DFS) 문제 요약 1. 주어진 이진 트리가 높이 균형이 맞는지 아닌지를 판별하는 프로그램을 작성하라. 2. 높이 균형이 맞는 이진 트리는 모든 노드들의 왼쪽 및 오른쪽 서브 트리의 높이 차이가 1을 초과하지 않는 트리를 의미한다. - 형제 노드 간의 차이가 1을 초과하지 않을 때는 True를, 그렇지 않은 경우에는 False를 반환하면 된다. 입출력 형태 - 예시 1의 경우 모든 서브트리에서 높이 차이가 최대 1이다. 그렇기 때문에 True를 반환하였다. - 예시 2의 경우 가장 하위에 있는 서브트리와([3, 4, 4])가 루트의 서브트리([1, 2, 2])와 높이 차이가 1을 초과하기 때문에 f..
[리트코드] Serialize and Deserialize Binary Tree(python) 리트코드, Serialize and Deserialize Binary Tree(이진 트리 직렬화와 역직렬화) TL;DR 트리(Tree) 문제 요약 1. 주어진 트리를 컴퓨터에서 다루기 쉬운 형태로 변형하는 직렬화(Serialize)하는 코드를 작성하라. 2. 직렬화된 트리를 다시 원래의 형태로 되돌리는 역직렬화(Deserialize)하는 코드를 작성하라. 3. 이진 트리를 입력받아 문자열 형태로 직렬화 해야 하고, 직렬화된 문자열을 다시 이진 트리로 역직렬화할 수 있어야 한다. - 트리와 같이 논리적인 데이터 구조를 갖고 있는 자료 구조를 컴퓨터 내부에 저장하기 위해서는 물리적인 구조로 바꾸어주어야 할 필요가 있다. 이 때, 논리적인 데이터 구조에서 물리적인 데이터 구조로 변경하는 작업을 직렬화(Seri..

티스토리툴바