트리32 [백준] 9934번: 완전 이진 트리 (C++) 9934번: 완전 이진 트리 문제) 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다. 상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 번호를 종이에 적어 놓았다. 한국으로 돌아온 상근이는 도시가 어떻게 생겼는지 그림을 그려보려고 하였으나, 정확하게 기억이 나지 않아 실패했다. 하지만, 어떤 순서로 도시를 방문했는지 기억해냈다. 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다. 현.. 2023. 7. 15. [백준] 1068번 : 트리 (C++) 10984번: 내 학점을 구해줘 문제 ) 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 입력 : 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면.. 2023. 5. 11. [백준] 3584번: 가장 가까운 공통 조상 (python) 3584번: 가장 가까운 공통 조상 문제 ) 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다. 예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다. 루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요 입력 : 첫 줄에 테스트 케이스의 개수.. 2022. 4. 27. [백준] 6615번: 콜라츠 추측 (python) 6615번: 콜라츠 추측 문제 ) 콜라츠 추측은 흥미로운 현상이다. 이 법칙은 간단해보이지만, 수학적으로 아직까지 증명되어있지 않은 문제이다. 우리는 이 추측이 옳다고 받아들이겠다. 콜라츠 추측을 설명하면 다음과 같다. 우선 다음과 같은 양의 정수 수열 xi 를 생각하자. 만약 xi 가 짝수이면, xi+1=xi/2 만약 xi 가 홀수이면, xi+1=3*xi +1 이다. 콜라츠 추측은 이렇게 만든 수열은 결국 1이 된다는 것이다. 과학자들은, 컴퓨터를 이용하여 첫 번째 수열이 258 보다 작으면, 이 추측은 참이라고 증명했다. 이제 문제를 보자. 두개의 양의 정수를 준다. 각각의 수에 대해서 콜라츠 추측으로 만든 수열을 생각하자. 각각의 수열을 비교하였을때 처음으로 같은 숫자가 나왔을때 , 각각 몇번째 수.. 2022. 4. 27. 이전 1 2 3 4 5 6 7 8 다음
